#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; }