#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 200005
#define fi first
#define se second
#define N 200000
int dizi[lim];
struct Node{
int val;
Node *left,*right;
Node(){
val=0;
left=NULL;
right=NULL;
}
Node(Node *tmp){
val=tmp->val;
left=tmp->left;
right=tmp->right;
}
};
inline void build(Node *node,int start,int end){
//cout<<start<<" "<<end<<endl;
if(start==end){
node->val=0;
return ;
}
node->left=new Node();
node->right=new Node();
build(node->left,start,mid),build(node->right,mid+1,end);
}
inline void update(Node *node,int start,int end,int l,int r,int val){
//cout<<start<<" "<<end<<" "<<l<<" "<<r<<" "<<val<<endl;
if(start>end || start>r || end<l || node==NULL)return ;
if(start>=l && end<=r){
node->val+=val;
return ;
}
if(l<=mid)node->left=new Node(node->left);
else node->right=new Node(node->right);
update(node->left,start,mid,l,r,val),update(node->right,mid+1,end,l,r,val);
node->val=node->left->val+node->right->val;
}
inline int query(Node *node,int start,int end,int l,int r){
if(start>end || start>r || end<l || node==NULL)return 0;
if(start>=l && end<=r){
return node->val;
}
return query(node->left,start,mid,l,r)+query(node->right,mid+1,end,l,r);
}
int32_t main(){
faster
int n,q;cin>>n>>q;
FOR{
cin>>dizi[i];
}
Node *tmp=new Node();
vector<Node*> roots;
build(tmp,1,N);
roots.push_back(tmp);
FOR{
tmp=new Node(roots[i-1]);
update(tmp,1,N,dizi[i],dizi[i],1);
roots.push_back(tmp);
}
while(q--){
int a,b;cin>>a>>b;
int l=1,r=N;
while(l<=r){
int m=(l+r)/2;
//cout<<query(roots[b],1,N,m,N)<<" "<<query(roots[a-1],1,N,m,N)<<" "<<m<<endl;
if(query(roots[b],1,N,m,N)-query(roots[a-1],1,N,m,N)>=m){
l=m+1;
}
else r=m-1;
}
cout<<r<<'\n';
}
return 0;
}
