#include <bits/stdc++.h> using namespace std; struct Fenwick { int n; vector<int> bit; Fenwick(int n=0): n(n), bit(n+1,0) {} void reset() { fill(bit.begin(), bit.end(), 0); } void add(int i, int v){ for(; i<=n; i+=i&-i) bit[i]+=v; } int sumPrefix(int i) const{ int s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; } int sumRange(int l,int r) const{ if(l>r) return 0; return sumPrefix(r)-sumPrefix(l-1); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,q; cin >> n >> q; vector<int> v(n+1); vector<pair<int,int>> papers; papers.reserve(n); for(int i=1;i<=n;i++){ cin >> v[i]; papers.push_back({v[i], i}); } sort(papers.begin(), papers.end(), [&](auto &a, auto &b){ return a.first > b.first; // descending by value }); vector<int> L(q), R(q); for(int i=0;i<q;i++){ cin >> L[i] >> R[i]; if(L[i] > R[i]) swap(L[i], R[i]); } // h is in [0..len], so search on [0..len+1) => lo inclusive, hi exclusive vector<int> lo(q, 0), hi(q); for(int i=0;i<q;i++){ int len = R[i]-L[i]+1; hi[i] = len + 1; } Fenwick fw(n); // buckets: mid -> list of queries vector<vector<int>> bucket(n+2); bool changed = true; while(changed){ changed = false; for(int m=0;m<=n+1;m++) bucket[m].clear(); int active = 0; for(int i=0;i<q;i++){ if(hi[i] - lo[i] > 1){ int mid = (lo[i] + hi[i]) >> 1; bucket[mid].push_back(i); active++; } } if(active == 0) break; fw.reset(); int pptr = 0; // pointer into papers (descending by value) // process mids from high to low so we only sweep papers once for(int mid=n+1; mid>=1; mid--){ // activate all positions with value >= mid while(pptr < n && papers[pptr].first >= mid){ fw.add(papers[pptr].second, 1); pptr++; } // answer all queries with this mid for(int qi : bucket[mid]){ int cnt = fw.sumRange(L[qi], R[qi]); // #papers with citations >= mid if(cnt >= mid) lo[qi] = mid; else hi[qi] = mid; changed = true; } } } for(int i=0;i<q;i++){ cout << lo[i] << "\n"; } return 0; }