#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int a,n,t,x,y,st,md,ed;
vector<int> v[200005];
struct node
{
int val;
node *l,*r;
};
typedef node* pnode;
void build(pnode tree,int st,int ed)
{
int md=(st+ed)/2;
if(st==ed)
{
tree->val=1;
return;
}
tree->l=new node(),tree->r=new node();
build(tree->l,st,md);
build(tree->r,md+1,ed);
tree->val=tree->l->val+tree->r->val;
}
void update(pnode tree,pnode pre,int st,int ed,int idx,int val)
{
int md=(st+ed)/2;
if(st==ed)
{
tree->val=pre->val+val;
return;
}
if(idx<=md)
{
// if(!tree->l)
// {
tree->l=new node();
// }else
// {
// tree->l=pre->l;
// }
tree->r=pre->r;
update(tree->l,pre->l,st,md,idx,val);
}else
{
tree->l=pre->l;
// if(!tree->r)
// {
tree->r=new node();
// }else
// {
// tree->r=pre->r;
// }
update(tree->r,pre->r,md+1,ed,idx,val);
}
tree->val=tree->l->val+tree->r->val;
}
int query(pnode tree,int st,int ed,int l,int r)
{
int md=(st+ed)/2;
if(st>r||ed<l)return 0;
if(st>=l&&ed<=r)return tree->val;
return query(tree->l,st,md,l,r)+query(tree->r,md+1,ed,l,r);
}
void debug(pnode tree,int st,int ed)
{
int md=(st+ed)/2;
if(st==ed)
{
printf("%d %d %d\n",st,ed,tree->val);
return;
}
debug(tree->l,st,md);
debug(tree->r,md+1,ed);
printf("%d %d %d\n",st,ed,tree->val);
}
node root[400005];
int checkpt[200005];
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n >> t;
build(&root[1],1,n);
/*debug(&root[1],1,n);
printf("query\n");
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
printf("%d %d %d\n",i,j,query(&root[1],1,n,i,j));
}
}*/
checkpt[1] = 1;
for(int i=1;i<=n;i++)
{
cin >> a;
v[a].pb(i);
}
int upd_num = 1;
for(int i=2;i<=200000;i++)
{
update(&root[upd_num+1],&root[upd_num],1,n,1,0); upd_num++;
for(int j=0;j<(int)v[i-1].size();j++)
{
int num=v[i-1][j];
update(&root[upd_num+1],&root[upd_num],1,n,num,-1); upd_num++;
// if(i==2)
// {
// printf("%d\n",j);
// debug(&root[1],1,n);
// }
}
checkpt[i] = upd_num;
}
/*for(int i=1;i<=8;i++)
{
printf("%d\n",i);
for(int j=1;j<=n;j++)
{
for(int k=j;k<=n;k++)
{
printf("%d %d %d\n",j,k,query(&root[i],1,n,j,k));
}
}
}*/
while(t--)
{
cin >> x >> y;
st=1,ed=200000;
while(ed>=st)
{
md=(st+ed)/2;
if(query(&root[checkpt[md]],1,n,x,y)>=md)
{
st=md+1;
}else
{
ed=md-1;
}
}
printf("%d\n", st-1);
/*for(int i=1;i<=8;i++)
{
printf("%d ",query(&root[i],1,n,x,y));
}
printf("\n");*/
//printf("%d %d %d\n",st,md,ed);
}
}
