题意：给一个 \(1\sim n\) 的排列，多次询问某段区间内的值域连续子区间的个数。
区间值域连续的另一种表达方式：\(max-min=r-l\)，即 \((max-min)-(r-l)=0\)。
考虑 \(l=1,r=n\) 怎么做，我们对 \(r\) 进行扫描线，维护有多少个 \(l\) 满足 \((max-min)-(r-l)=0\)。
看起来是很难维护的，但实际上可以发现 \((max-min)-(r-l)\geq 0\)，而且必然至少一个 \(l\) 使得 \((max-min)-(r-l)=0\)（如平凡的 \(l=r\) 的情况），那么我们考虑用线段树维护 \((max-min)-(r-l)\) 的最小值以及最小值的个数（根据刚刚说的，全局最小值的个数就是 \((max-min)-(r-l)=0\) 的个数），然后对于每个 \(r\) 统计即可。
至于动态维护 \((max-min)-(r-l)\)，我们可以用单调栈记录不同 \(max\) 值的区间，并动态维护（\(min\) 值同理）。
那么多次询问区间怎么办呢？我们可以先把询问离线下来，然后同样对 \(r\) 进行扫描线，那么询问时要知道一段区间历史上为最小值的时间有多少，可以用懒标记维护。
具体来说，对于每一个点 \(u\) 设一个 \(tag\) 表示 \(u\) 子树内的所有最小值在历史上有 \(tag\) 时间也是最小值。
当要修改点 \(u\) 子树内的某个点时，由于 \(u\) 子树内的最小值可能变化，所以要向儿子下传标记（需要判断儿子子树内的最小值是否等于 \(u\) 子树内的最小值）。
代码如下：
#include<bits/stdc++.h>
#define N 120010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Query
{
int l,r,id;
}q[N];
bool operator < (Query a,Query b)
{
return a.r<b.r;
}
int n,m,p[N];
int topmax,smax[N];
int topmin,smin[N];
int minn[N<<2],cnt[N<<2],tagmin[N<<2];
ll ans[N<<2],tagans[N<<2];
ll Ans[N<<2];
void downmin(int k,int v)
{
minn[k]+=v,tagmin[k]+=v;
}
void downans(int k,int v)
{
ans[k]+=1ll*cnt[k]*v,tagans[k]+=v;
}
void down(int k)
{
if(tagmin[k])
{
downmin(k<<1,tagmin[k]);
downmin(k<<1|1,tagmin[k]);
tagmin[k]=0;
}
if(tagans[k])
{
if(minn[k]==minn[k<<1]) downans(k<<1,tagans[k]);
if(minn[k]==minn[k<<1|1]) downans(k<<1|1,tagans[k]);
tagans[k]=0;
}
}
void up(int k)
{
if(minn[k<<1]==minn[k<<1|1]) minn[k]=minn[k<<1],cnt[k]=cnt[k<<1]+cnt[k<<1|1];
else if(minn[k<<1]<minn[k<<1|1]) minn[k]=minn[k<<1],cnt[k]=cnt[k<<1];
else minn[k]=minn[k<<1|1],cnt[k]=cnt[k<<1|1];
}
void build(int k,int l,int r)
{
if(l==r)
{
minn[k]=l;
cnt[k]=1;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
void update(int k,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr)
{
downmin(k,v);
return;
}
down(k);
int mid=(l+r)>>1;
if(ql<=mid) update(k<<1,l,mid,ql,qr,v);
if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,v);
up(k);
}
ll query(int k,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return ans[k];
down(k);
int mid=(l+r)>>1;
ll res=0;
if(ql<=mid) res+=query(k<<1,l,mid,ql,qr);
if(qr>mid) res+=query(k<<1|1,mid+1,r,ql,qr);
return res;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) p[i]=read();
m=read();
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1);
build(1,1,n);
int tmp=1;
for(int i=1;i<=n;i++)
{
update(1,1,n,1,n,-1);
while(topmax&&p[i]>p[smax[topmax]])
{
update(1,1,n,smax[topmax-1]+1,smax[topmax],p[i]-p[smax[topmax]]);
topmax--;
}
smax[++topmax]=i;
while(topmin&&p[i]<p[smin[topmin]])
{
update(1,1,n,smin[topmin-1]+1,smin[topmin],p[smin[topmin]]-p[i]);
topmin--;
}
smin[++topmin]=i;
downans(1,1);
while(tmp<=m&&q[tmp].r==i)
{
Ans[q[tmp].id]=query(1,1,n,q[tmp].l,q[tmp].r);
tmp++;
}
}
for(int i=1;i<=m;i++)
printf("%lld\n",Ans[i]);
return 0;
}