#include<cstdio>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define int long long
vector<int> sortx;
int N,Q,x[100010],lookup[100010],root,sz;
struct range{
int s,e,v;
range(){}
range(int s_,int e_):s(s_),e(e_){}
}z[100010];
bool cmp(range a,range b){return (a.s/root)*2*root+a.e/root<(b.s/root)*2*root+b.e/root;}
struct ans{
int ret,v;
ans(){}
ans(int ret_,int v_):ret(ret_),v(v_){}
}A[100010];
bool cmp2(ans a,ans b){return a.v<b.v;}
int tree[400010];
void push(int x,int add){
tree[x]+=add;
for(int i=x/2;i>0;i>>=1){
tree[i]=max(tree[i*2],tree[i*2+1]);
}
}
main(){
int t;
scanf("%lld%lld",&N,&Q);
root=300;
sz=1;
while(sz<N)sz<<=1;
for(int i=1;i<=N;i++)scanf("%lld",&x[i]);
for(int i=0;i<Q;i++)scanf("%lld%lld",&z[i].s,&z[i].e),z[i].v=i;
for(int i=1;i<=N;i++)sortx.push_back(x[i]);
sort(sortx.begin(),sortx.end());
sortx.erase(unique(sortx.begin(),sortx.end()),sortx.end());
for(int i=1;i<=N;i++){
t=x[i];
x[i]=lower_bound(sortx.begin(),sortx.end(),x[i])-sortx.begin();
lookup[x[i]]=t;
}
sort(z,z+Q,cmp);
int L,R;
L=z[0].s;
R=z[0].s-1;
for(int i=0;i<Q;i++){
if(R<z[i].e){for(int j=R+1;j<=z[i].e;j++)push(x[j]+sz,lookup[x[j]]);R=z[i].e;}
else if(R>z[i].e){for(int j=R;j>z[i].e;j--)push(x[j]+sz,-lookup[x[j]]);R=z[i].e;}
if(L<z[i].s){for(int j=L;j<z[i].s;j++)push(x[j]+sz,-lookup[x[j]]);L=z[i].s;}
else if(L>z[i].s){for(int j=L-1;j>=z[i].s;j--)push(x[j]+sz,lookup[x[j]]);L=z[i].s;}
A[i]=ans(tree[1],z[i].v);
}
sort(A,A+Q,cmp2);
for(int i=0;i<Q;i++)printf("%lld ",A[i].ret);
}
