#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define ld long double #define sz(x) static_cast<int>((x).size()) #define i5 tuple<int,int,int,int,int> #define all(x) x.begin(), x.end() #define iiii tuple<int, int,int,int> #define ld long double #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> signed main(){ int n,q;cin>>n>>q; vector<int> v(n+1), ans(q, 0); vector<pll> pos; for(int i=1;i<=n;i++){ cin>>v[i]; pos.pb({v[i], i}); } sort(all(pos)); vector<pll> qs(q); for(int i=0;i<q;i++)cin>>qs[i].f>>qs[i].s; queue<tuple<int,int,vector<int>>> que; vector<int> temp(q); iota(all(temp),0); que.push(make_tuple(1, n+1, temp)); ordered_set oset; int ptr=n; while(!que.empty()){ auto [lo, hi, cq] = que.front(); que.pop(); int m=(lo+hi)/2; //printf("\nlo %lld hi %lld\n", lo, hi); if(hi <= lo + 1){ for(auto it:cq)ans[it]=lo; continue; } else { if (ptr < 0 or pos[ptr].f < m){//reset ptr=n-1; oset.clear(); } while (ptr >= 0 and pos[ptr].f >= m){ oset.insert(pos[ptr].s); ptr--; } vector<int> l, r; for(auto it:cq){ int num=oset.order_of_key(qs[it].s+1) - oset.order_of_key(qs[it].f); //printf("query from %lld to %lld, num is %lld\n", qs[it].s, qs[it].f, num); if(num >= m)r.pb(it); else l.pb(it); } if(!r.empty())que.push(make_tuple(m, hi, r)); if(!l.empty())que.push(make_tuple(lo, m, l)); } } for(int i=0;i<q;i++){ cout<<ans[i]<<"\n"; } }