题解：
和这件zhcs的那题有点像
第一种做法是考虑i,i+1之间的贡献
这样子就是矩形加减然后求矩形最小值个数
另一种做法是我们从左向右维护mx-nx-r+l
跟之前那题一样我们知道这个的最小值为0
另外我们只需要从右向左维护一个单调队列，这样区间取min/max（每个数插入删除一次）
就可以变成分段区间+/-操作了
然后这样就变成区间+/-然后查询历史为0的个数
其实这等价于上一种+扫描线
之后这个地方非常套路。。刚开始并没有理解
首先每个点肯定要维护最小值以及最小值个数
我们对每个点再维护一个时间标记，表示这个点是0的时间
注意我们不能去记录这个时间节点是多少
因为这样标记无法合并，我们在区间修改了一个节点后，我们不能即时的对子区间进行修改
然后下一个标记打下来就出错了
我们去记录每个点为0的时间，并且在父亲方向上可以打增加时间的标记
如何在增加了标记之后下传呢
我们考虑这个点以上的标记影响的都是这整个区间
这个区间之前最小值为0的位置，现在也一定是最小值
所以我们判一下它和父亲最小值是否相同就可以了
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define ll long long
#define mep(x,y) memcpy(x,y,sizeof(y))
#define mid ((h+t)>>1)
namespace IO{
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
char sr[<<],z[]; int Z,C=-;
template<class T>void wer(T x)
{
if (x<) sr[++C]='-',x=-x;
while (z[++Z]=x%+,x/=);
while (sr[++C]=z[Z],--Z);
}
IL void wer1() { sr[++C]=' ';}
IL void wer2() { sr[++C]='\n';}
template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}
template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
template<class T>IL T MAX(T x,T y) {return x>y?x:y;}
template<class T>IL T MIN(T x,T y) {return x<y?x:y;}
};
using namespace IO;
const int N=1.5e5;
int v[N],q,n,pos[N],cnt,p[N];
struct re{
int a,b,c,d;
}a[N*],b[N*];
ll ans[N*];
void change(int x1,int x2,int y1,int y2,int k)
{
b[++cnt]=(re){x1,y1,y2,k};
b[++cnt]=(re){x2+,y1,y2,-k};
}
const int N1=N*;
struct sgt{
ll now[N1];
int tim[N1],num[N1],v[N1],lazy[N1];
void build(int x,int h,int t)
{
num[x]=(t-h+);
if (h==t) return;
build(x*,h,mid); build(x*+,mid+,t);
}
IL void down(int x)
{
if (lazy[x])
{
lazy[x*]+=lazy[x]; lazy[x*+]+=lazy[x];
v[x*]+=lazy[x]; v[x*+]+=lazy[x];
lazy[x]=;
}
if (tim[x])
{
if (v[x*]==v[x])
{
now[x*]+=1ll*tim[x]*num[x*];
tim[x*]+=tim[x];
}
if (v[x*+]==v[x])
{
now[x*+]+=1ll*tim[x]*num[x*+];
tim[x*+]+=tim[x];
}
tim[x]=;
}
}
IL void updata(int x)
{
now[x]=now[x*]+now[x*+];
v[x]=MIN(v[x*],v[x*+]);
num[x]=;
if (v[x]==v[x*]) num[x]+=num[x*];
if (v[x]==v[x*+]) num[x]+=num[x*+];
}
void change(int x,int h,int t,int h1,int t1,int k)
{
if (h1<=h&&t<=t1)
{
v[x]+=k; lazy[x]+=k; return;
}
down(x);
if (h1<=mid) change(x*,h,mid,h1,t1,k);
if (mid<t1) change(x*+,mid+,t,h1,t1,k);
updata(x);
}
ll query(int x,int h,int t,int h1,int t1)
{
if (h1<=h&&t<=t1) return(now[x]);
down(x);
ll ans=;
if (h1<=mid) ans+=query(x*,h,mid,h1,t1);
if (mid<t1) ans+=query(x*+,mid+,t,h1,t1);
return ans;
}
}S;
bool cmp(re x,re y)
{
return x.a<y.a;
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n);
rep(i,,n) read(v[i]),pos[v[i]]=i;
rep(i,,n-)
{
change(,i,i+,n,);
change(i+,n,,i,);
int x1=pos[i],x2=pos[i+];
if (x1>x2) swap(x1,x2);
change(,x1,x2,n,-);
change(x2,n,,x1,-);
}
read(q);
int q1=q*;
rep(i,,q)
{
int x,y;
read(x); read(y);
a[i*-]=(re){y,y,i*-};
a[i*-]=(re){x-,y,i*-};
a[i*-]=(re){y,x-,i*-};
a[i*]=(re){x-,x-,i*};
p[i]=y-x+;
}
int now=,lst=;
S.build(,,n);
sort(a+,a+q1+,cmp);
sort(b+,b+cnt+,cmp);
rep(i,,q1)
{
while(now<=cnt&&b[now].a<=a[i].a)
{
S.tim[]+=b[now].a-lst; S.now[]+=1ll*(b[now].a-lst)*S.num[];
lst=b[now].a;
S.change(,,n,b[now].b,b[now].c,b[now].d);
now++;
}
S.tim[]+=a[i].a+-lst; S.now[]+=1ll*(a[i].a+-lst)*S.num[];
lst=a[i].a+;
if (a[i].b) ans[a[i].c]=S.query(,,n,,a[i].b);
}
rep(i,,q)
wer((ans[i*-]-ans[i*-]-ans[i*-]+ans[i*]-p[i])/+p[i]),wer2();
fwrite(sr,,C+,stdout);
return ;
}