把询问看成二维点，建立kd-tree，每个点维护一个计数器。
从1到n依次加入每个数，每次加入一个数时，对于所有包含它的询问，计数器加一，对于其它询问，计数器置0。
那么每个询问的答案就是计数器的历史最大值，可以通过打标记实现。
时间复杂度$O(n\sqrt{m})$。
#include<cstdio>
#include<algorithm>
const int N=50010,inf=-1,BUF=2000000;
int n,m,i,x,id[N],root,cmp_d,X,a[N];char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
struct node{int D[2],l,r,Max[2],Min[2];int m,d,e,hm,hd,he;
}t[N];
inline bool cmp(const node&a,const node&b){return a.D[cmp_d]<b.D[cmp_d];}
inline void Max(int&a,int b){if(a<b)a=b;}
inline void Min(int&a,int b){if(a>b)a=b;}
inline void up(int x){id[t[x].e]=x,t[x].e=t[x].he=inf;if(t[x].l){Max(t[x].Max[0],t[t[x].l].Max[0]);Min(t[x].Min[0],t[t[x].l].Min[0]);Max(t[x].Max[1],t[t[x].l].Max[1]);Min(t[x].Min[1],t[t[x].l].Min[1]);}if(t[x].r){Max(t[x].Max[0],t[t[x].r].Max[0]);Min(t[x].Min[0],t[t[x].r].Min[0]);Max(t[x].Max[1],t[t[x].r].Max[1]);Min(t[x].Min[1],t[t[x].r].Min[1]);}
}
int build(int l,int r,int D){int mid=(l+r)>>1;cmp_d=D,std::nth_element(t+l+1,t+mid+1,t+r+1,cmp);t[mid].Max[0]=t[mid].Min[0]=t[mid].D[0];t[mid].Max[1]=t[mid].Min[1]=t[mid].D[1];if(l!=mid)t[mid].l=build(l,mid-1,!D);if(r!=mid)t[mid].r=build(mid+1,r,!D);return up(mid),mid;
}
inline void hdoa(node&x,int v){Max(x.hm,x.m+v);if(x.e>inf)Max(x.he,x.e+v);else Max(x.hd,x.d+v);
}
inline void hdoc(node&x,int v){Max(x.hm,v);Max(x.he,v);}
inline void doa(node&x,int v){Max(x.hm,x.m+=v);if(x.e>inf)Max(x.he,x.e+=v);else Max(x.hd,x.d+=v);
}
inline void doc(node&x,int v){Max(x.hm,x.m=v);Max(x.he,x.e=v);x.d=0;}
inline void pb(node&x){if(x.hd){if(x.l)hdoa(t[x.l],x.hd);if(x.r)hdoa(t[x.r],x.hd);x.hd=0;}if(x.he>inf){if(x.l)hdoc(t[x.l],x.he);if(x.r)hdoc(t[x.r],x.he);x.he=inf;}if(x.d){if(x.l)doa(t[x.l],x.d);if(x.r)doa(t[x.r],x.d);x.d=0;}else if(x.e>inf){if(x.l)doc(t[x.l],x.e);if(x.r)doc(t[x.r],x.e);x.e=inf;}
}
void change(node&x){if(x.Min[0]>X||x.Max[1]<X){doc(x,0);return;}if(x.Max[0]<=X&&x.Min[1]>=X){doa(x,1);return;}pb(x);if(x.D[0]<=X&&x.D[1]>=X)Max(x.hm,++x.m);else x.m=0;if(x.l)change(t[x.l]);if(x.r)change(t[x.r]);
}
void dfs(node&x){pb(x);if(x.l)dfs(t[x.l]);if(x.r)dfs(t[x.r]);
}
int main(){fread(Buf,1,BUF,stdin),read(n),read(m);for(i=1;i<=n;i++)read(X),a[X]=i;for(i=1;i<=m;i++)read(t[i].D[0]),read(t[i].D[1]),t[i].e=i;root=build(1,m,1);for(i=1;i<=n;i++)X=a[i],change(t[root]);dfs(t[root]);for(i=1;i<=m;i++)printf("%d\n",t[id[i]].hm);return 0;
}