#include <bits/stdc++.h>
using namespace std;
struct Node{
Node *l,*r;int sum;
Node(int val):l(nullptr),r(nullptr),sum(val){}
Node(Node *l,Node *r):l(l),r(r),sum(0){
if (l!=nullptr) sum+=l->sum;
if (r!=nullptr) sum+=r->sum;
}
Node(Node *cp):l(cp->l),r(cp->r),sum(cp->sum){}
};
#define MAXN 200001
int n,q;
Node* root[MAXN];
Node* build(int l,int r)
{
if (l==r) return new Node(0);
int mid=(l+r)/2;return new Node(build(l,mid),build(mid+1,r));
}
Node* update(Node* node,int l,int r,int pos,int val)
{
if (l==r) return new Node(node->sum+val);
int mid=(l+r)/2;
if (pos<=mid) return new Node(update(node->l,l,mid,pos,val),node->r);
else return new Node(node->l,update(node->r,mid+1,r,pos,val));
}
int query(Node* node,int l,int r,int a,int b)
{
if (a>b) return 0;
if (l==a and r==b) return node->sum;
int mid=(l+r)/2;
return query(node->l,l,mid,a,min(b,mid))+query(node->r,mid+1,r,max(a,mid+1),b);
}
int main()
{
ios_base::sync_with_stdio(false);ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);cin>>n>>q;root[0]=build(1,200000);int maks=0;
for (int i=1;i<=n;i++) {int x;cin>>x;root[i]=update(root[i-1],1,n,x,1);maks=max(maks,x);}
for (int i=1;i<=q;i++)
{
int levo,desno;cin>>levo>>desno;
int l=2,r=desno-levo+1,rez=1;
while (l<=r)
{
int mid=(l+r)/2;
if (query(root[desno],1,n,mid,maks)-query(root[levo-1],1,n,mid,maks)>=mid) {rez=mid;l=mid+1;}
else r=mid-1;
}
cout<<rez<<endl;
}
}
