#include <bits/stdc++.h>
#define N 200005
using namespace std;
int arr[N];
int cnt[N];
struct Node{
int sum=0;
Node *lc=NULL,*rc=NULL;
Node(int a){
sum = a;
}
Node(Node *a, Node *b){
if(a != NULL)sum += a->sum;
if(b != NULL)sum += b->sum;
lc = a;
rc = b;
}
};
Node* build(int l,int r){
if(l == r){
return new Node(cnt[l]);
}
int m = (l+r)/2;
return new Node(build(l,m),build(m+1,r));
}
Node* upd(Node* v,int l,int r,int pos,int val){
if(l == r){
return new Node(v->sum + val);
}
int m = (l+r)/2;
if(pos <=m){
return new Node(upd(v->lc,l,m,pos,val),v->rc);
}
else return new Node(v->lc,upd(v->rc,m+1,r,pos,val));
}
int get(Node* v1,Node* v2,int tl,int tr, int l){
if(tr < l){
return 0;
}
if(l <= tl){
return v1->sum - v2 -> sum;
}
int tm = (tl+tr)/2;
return get(v1->lc,v2->lc,tl,tm,l) + get(v1->rc,v2->rc,tm+1,tr,l);
}
int get(Node* v,int tl,int tr, int l){
if(tr < l){
return 0;
}
if(l <= tl){
return v->sum;
}
int tm = (tl+tr)/2;
return get(v->lc,tl,tm,l) + get(v->rc,tm+1,tr,l);
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
cnt[arr[i]]++;
}
vector<Node *> roots;
roots.push_back(build(1,N-1));
for(int i=1;i<n;i++){
roots.push_back(upd(roots[i-1],1,N-1,arr[i-1],-1));
}
while(q--){
int ql,qr;
scanf("%d%d",&ql,&qr);
ql--,qr--;
int l = 1,r = qr-ql+1;
while(l < r){
int m = (l+r+1)/2;
int val;
if(qr +1 != n){
val = get(roots[ql],roots[qr+1],1,N-1,m);
}
else val = get(roots[ql],1,N-1,m);
if(val >= m){
l = m;
}
else r = m-1;
}
printf("%d\n",l);
}
}
