#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
const int MAXP = 300000;
const int MAXNODES = 7000000;
int L[MAXNODES], R[MAXNODES], val[MAXNODES];
int sz = 0;
int root[MAXN + 5];
int new_node(){
++sz;
L[sz] = R[sz] = val[sz] = 0;
return sz;
}
int update(int prev, int l, int r, int pos){
int cur = new_node();
L[cur] = L[prev];
R[cur] = R[prev];
val[cur] = val[prev] + 1;
if(l == r) return cur;
int mid = (l + r) >> 1;
if(pos <= mid) L[cur] = update(L[prev], l, mid, pos);
else R[cur] = update(R[prev], mid+1, r, pos);
return cur;
}
int query(int u, int v, int l, int r, int ql, int qr){
if(ql > r || qr < l) return 0;
if(ql <= l && r <= qr) return val[u] - val[v];
int mid = (l + r) >> 1;
return query(L[u], L[v], l, mid, ql, qr) + query(R[u], R[v], mid+1, r, ql, qr);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
if(!(cin >> n >> q)) return 0;
vector<int> p(n+1);
for(int i=1;i<=n;i++) cin >> p[i];
sz = 0;
new_node();
root[0] = 0;
for(int i=1;i<=n;i++){
root[i] = update(root[i-1], 1, MAXP, p[i]);
}
while(q--){
int l, r;
cin >> l >> r;
int len = r - l + 1;
int lo = 1, hi = min(len, MAXP), ans = 0;
while(lo <= hi){
int mid = (lo + hi) >> 1;
int cnt = 0;
if(mid <= MAXP) cnt = query(root[r], root[l-1], 1, MAXP, mid, MAXP);
if(cnt >= mid){
ans = mid;
lo = mid + 1;
} else hi = mid - 1;
}
cout << ans << '\n';
}
return 0;
}
