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