#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int N=200000;
struct Node{
int val=0;
Node *l=NULL,*r=NULL;
};
void build(Node *node,int l,int r){
if(l==r)return;
int mid=(l+r)/2;
node->l=new Node;
node->r=new Node;
build(node->l,l,mid);
build(node->r,mid+1,r);
return;
}
void update(Node *node,Node *pre,int l,int r,int x,int y){
if(l==r){
node->val=y;
return;
}
int mid=(l+r)/2;
if(x<=mid){
node->r=pre->r;
node->l=new Node;
update(node->l,pre->l,l,mid,x,y);
}
else{
node->l=pre->l;
node->r=new Node;
update(node->r,pre->r,mid+1,r,x,y);
}
node->val=node->l->val+node->r->val;
return;
}
int query(Node *node,Node *pre,int l,int r,int k){
if(l==r){
return l;
}
int mid=(l+r)/2;
if(node->r->val-pre->r->val+k>=mid+1){
return query(node->r,pre->r,mid+1,r,k);
}
return query(node->l,pre->l,l,mid,k+node->r->val-pre->r->val);
}
int32_t main(){
fast;
int n,q;
cin>>n>>q;
vector<int>arr(n+1);
for(int i=1;i<=n;i++){
cin>>arr[i];
}
vector<Node*>pre(n+1);
pre[0]=new Node;
build(pre[0],1,N);
vector<int>cnt(N+1);
for(int i=1;i<=n;i++){
cnt[arr[i]]++;
pre[i]=new Node;
update(pre[i],pre[i-1],1,N,arr[i],cnt[arr[i]]);
}
while(q--){
int l,r;
cin>>l>>r;
cout<<query(pre[r],pre[l-1],1,N,0)<<endl;
}
}
