#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MAX = 200'000;
struct Node{
int seg;
int L, R;
Node (){
seg = 0;
L = 0;
R = 0;
}
};
vector<Node> S = {Node()};
int n;
//pos[x]++ na subarvore p de range [l,r]
int update(int p, int x){
int l = 1, r = MAX;
int root = S.size();
while(true){
S.push_back(S[p]);
p = S.size()-1;
S[p].seg++;
if(l == r)break;
int m = (l+r)/2;
if(x <= m){
tie(p,S[p].L) = make_tuple(S[p].L,S.size());
r = m;
}
else{
tie(p,S[p].R) = make_tuple(S[p].R,S.size());
l = m+1;
}
}
return root;
}
int bs(int pl, int pr){
int l = 1, r = MAX;
int cur = 0;
while(l!=r){
int m = (l+r)/2;
int val = S[S[pr].R].seg-S[S[pl].R].seg;
if(val+cur < m+1){
cur += val;
r = m;
pl = S[pl].L;
pr = S[pr].L;
}else{
l = m+1;
pl = S[pl].R;
pr = S[pr].R;
}
}
return r;
}
int main() { //_
int n,q;
cin >> n >> q;
vector<int> rts(n+1);
for(int i = 1; i <= n; i++){
int p;
cin >> p;
rts[i] = update(rts[i-1],p);
}
while(q--){
int l,r;
cin >> l >> r;
cout << bs(rts[l-1],rts[r]) << '\n';
}
}
