#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000007
#define int long long
int n,q;
int arr[200001];
struct node{
node *Left,*Right;
int sum=0;
};
node *rt[200001];
void set_initially(int l1,int r1,node *curr){
if(l1==r1) return;
curr->Left=new node();
curr->Right=new node();
set_initially(l1,(l1+r1)/2,curr->Left);
set_initially((l1+r1)/2+1,r1,curr->Right);
return;
}
int solve(int l1,int r1,int l,int r,node *currL,node *currR){
if(l1>r||l>r1) return 0;
if(l<=l1&&r1<=r) return currR->sum - currL->sum;
return solve(l1,(l1+r1)/2,l,r,currL->Left,currR->Left)+solve((l1+r1)/2+1,r1,l,r,currL->Right,currR->Right);
}
node* update(int l1,int r1,int x,node *curr){
if(l1==r1){
node *nw=new node();
nw->sum=curr->sum+1;
return nw;
}
node *nw=new node();
if(x<=(l1+r1)/2){
nw->Right=curr->Right;
nw->Left=update(l1,(l1+r1)/2,x,curr->Left);
}
else{
nw->Left=curr->Left;
nw->Right=update((l1+r1)/2+1,r1,x,curr->Right);
}
nw->sum=nw->Left->sum+nw->Right->sum;
return nw;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q;
rt[0]=new node();
set_initially(0,2e5,rt[0]);
for(int i=1;i<=n;i++){
cin>>arr[i];
rt[i]=update(0,2e5,arr[i],rt[i-1]);
}
//cout<<solve(1,2e5,3,2e5,rt[0],rt[1])<<endl;
while(q--){
int i,j;
cin>>i>>j;
i--;
int l=0,r=2e5,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(solve(0,2e5,mid,2e5,rt[i],rt[j])>=mid){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
//g++ -std=c++17 template.cpp -o executable.exe
