#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define carp(x,y,mod) ((x%mod)*(y%mod))%mod
#define topla(x,y,mod) ((x%mod)+(y%mod))%mod
const int MAXN=2e5+5;
const int INF=1e9+1;
#define mid (l+r)/2
#define endl '\n'
int n,q;
vi a;
struct Dug{
Dug *l;
Dug *r;
int sm;
Dug(int val) : l(nullptr), r(nullptr), sm(val) {}
Dug(Dug* l, Dug* r) : l(l), r(r), sm(0){
if(l) sm+=l->sm;
if(r) sm+=r->sm;
}
Dug(Dug* kopya) : l(kopya->l), r(kopya->r), sm(kopya->sm) {}
};
Dug *root[MAXN];
Dug *build(int l=1,int r=n){
if(l==r) return new Dug(0);
auto sol=build(l,mid);
auto sag=build(mid+1,r);
return new Dug(sol,sag);
}
Dug *update(int pos,int val,Dug* nd,int l=1,int r=n){
if(l==r){
return new Dug(val);
}
if(pos<=mid){
auto sol=update(pos,val,nd->l,l,mid);
return new Dug(sol,nd->r);
}
else{
auto sag=update(pos,val,nd->r,mid+1,r);
return new Dug(nd->l,sag);
}
}
int query(int elde,Dug *bir,Dug *iki,int l=1,int r=n){
if(l==r){
return l;
}
int deg=(iki->r->sm)-(bir->r->sm);
if(deg>=mid+1-elde) return query(elde,bir->r,iki->r,mid+1,r);
else return query(elde+deg,bir->l,iki->l,l,mid);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
a.resize(n+1);
FORE(i,1,n+1) cin>>a[i];
root[0]=build();
map<int,int> cnt;
FORE(i,1,n+1){
cnt[a[i]]++;
root[i]=update(a[i],cnt[a[i]],root[i-1]);
}
while(q--){
int l,r;
cin>>l>>r;
cout<<query(0,root[l-1],root[r])<<endl;
}
}
