#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
const int sz = 200005;
int n, Q, c[sz], tree[sz*3], ans[sz];
struct query{
int l, r, index;
} q[sz];
bool cmp(query &a, query &b){
if(a.l/600 != b.l/600) return a.l/600 < b.l/600;
return a.r/600 < b.r/600;
}
/*
1 1000
300 500
1) 1000 + 800 = 1800
2) 500 + 800 = 1300
*/
inline void update(int l, int r, int node, int x, int val){
if(l > r || l > x || r < x) return;
if(l == r){
tree[node] += val;
return;
}
int mid = l + ((r - l) >> 1);
if(x <= mid) update(l, mid, node << 1, x, val);
else update(mid + 1, r, node << 1 | 1, x, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
return;
}
int get(int l, int r, int node, int L, int R){
if(l > r || l > R || r < L) return 0;
if(l >= L && r <= R) return tree[node];
int mid = l + ((r - l) >> 1);
return get(l, mid, node << 1, L, R) + get(mid + 1, r, node << 1 | 1, L, R);
}
inline void add(int x){
update(1, n, 1, x, 1);
return;
}
inline void del(int x){
update(1, n, 1, x, -1);
return;
}
int main(){
speed;
cin >> n >> Q;
for(register int i = 1; i <= n; ++i){
cin >> c[i];
}
for(register int i = 1; i <= Q; ++i){
cin >> q[i].l >> q[i].r, q[i].index = i;
}
sort(q+1,q+Q+1,cmp);
int l(1), r(0);
for(register int i = 1; i <= Q; ++i){
while(r < q[i].r) add(c[++r]);
while(r > q[i].r) del(c[r--]);
while(l < q[i].l) del(c[l++]);
while(l > q[i].l) add(c[--l]);
int L(1), R{r - l + 1}, mid, best;
while(L <= R){
mid = L + ((R - L) >> 1);
if(get(1, n, 1, mid, n) >= mid){
best = mid, L = mid + 1;
}else{
R = mid - 1;
}
}
ans[q[i].index] = best;
}
for(register int i = 1; i <= Q; ++i){
cout << ans[i] << '\n';
}
return 0;
}
