#include <bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; const int N = 200005; int n,q,ar[N+3]; vector<int>seg[4*N+3]; void build(int i,int l,int r){ if(l==r){ seg[i].emplace_back(ar[l]); return; } int mid=l+(r-l)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); seg[i].reserve(seg[i*2].size()+seg[i*2+1].size()); merge(seg[i*2].begin(),seg[i*2].end(),seg[i*2+1].begin(),seg[i*2+1].end(),back_inserter(seg[i])); } int que(int i,int l,int r,int ql,int qr,int x){ if(r<ql||l>qr)return 0; else if(l>=ql&&r<=qr){ int it=lower_bound(seg[i].begin(),seg[i].end(),x)-seg[i].begin(); return seg[i].size()-it; } int mid=l+(r-l)/2; return que(i*2,l,mid,ql,qr,x)+que(i*2+1,mid+1,r,ql,qr,x); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>ar[i]; } build(1,1,n); while(q--){ int L,R;cin>>L>>R; int l=1,r=R-L+1,ans=0; while(l<=r){ int mid=l+(r-l)/2; if(que(1,1,n,L,R,mid)>=mid){ ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; } } /* */