///0-0 : what is your motivation, quan606303? ///quan606303 : Hutao /*idea : */ #include <bits/stdc++.h> #define int long long #define ll long long #define INTMAX INT_MAX #define INTMIN INT_MIN #define LONGMAX LLONG_MAX #define LONGMIN LLONG_MIN #define fi first #define se second #define memfull(a,b) memset(a,b,sizeof(a)); #define endl '\n' #define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout); using namespace std; const int MOD=1e9+7; const int maxn=200005; int BIT[maxn]; int n,q; pair<int,int> a[maxn]; void upd(int x,int cnt) { for (;x<maxn;x+=(x&-x))BIT[x]+=cnt; } int get(int x) { int sum=0; for (;x>0;x&=(x-1))sum+=BIT[x]; return sum; } int get_range(int l,int r) { return get(r)-get(l-1); } int l[maxn],r[maxn],ans[maxn]; pair<int,int> b[maxn]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for (int i=1;i<=n;i++) { cin>>a[i].fi; a[i].se=i; } sort(a+1,a+1+n); for (int i=1;i<=q;i++) { cin>>b[i].fi>>b[i].se; l[i]=1; r[i]=n; ans[i]=0; } vector<vector<int> > queries; bool process=true; while (process) { process=false; queries.assign(n+5,vector<int>()); for (int i=1;i<=q;i++) { if (l[i]>r[i])continue; process=true; int mid=(l[i]+r[i])/2; queries[mid].push_back(i); } vector<int> vt; for (int mid=n,i=n;mid>=1;mid--) { while (i>=1&&a[i].fi>=mid) { upd(a[i].se,1); vt.push_back(a[i].se); i--; } int cnt=get_range(b[mid].fi,b[mid].se); for (auto c:queries[mid]) { int cnt=get_range(b[c].fi,b[c].se); if (cnt>=mid) { l[c]=mid+1; ans[c]=mid; } else r[c]=mid-1; } } for (auto i:vt)upd(i,-1); queries.clear(); } for (int i=1;i<=q;i++)cout<<ans[i]<<endl; return 0; }