#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 2*1e5+5;
pair<int,int> v[MAXN];
vector< vector< int> > que[2];
vector< int > l[2],r[2];
int bit[MAXN], a[MAXN], b[MAXN], ans[MAXN], n;
void update(int i){
for(; i <= n; i+= i&(-i))
bit[i]++;
}
int query(int i){
int ans = 0;
for(; i > 0; i-= i&(-i))
ans += bit[i];
return ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int q; cin>>n>>q;
for(int i = 1; i <= n; i++){
cin>>v[i].fi;
v[i].sc = i;
}
sort(v+1,v+1+n);
que[0].push_back({});
for(int i = 1;i <= q; i++){
cin>>a[i]>>b[i];
que[0][0].push_back(i);
}
l[0].push_back(1); r[0].push_back(n);
int niv = 0;
while(sz(l[niv]) != n){
for(int i = 1; i <= n; i++)bit[i] = 0;
int cur = n, nxt = niv^1;
for(int j = 0; j < sz(l[niv]); j++){
int mid = ( l[niv][j] + r[niv][j] +1) /2;
while(cur > 0 && v[cur].fi >= mid){
update(v[cur].sc);
cur--;
}
vector< int > menor = {}, maior = {};
for(int k = 0; k < sz(que[niv][j]); k++){
int temp = query( b[ que[niv][j][k] ] ) - query( a[ que[niv][j][k] ] -1);
if(temp >= mid) maior.push_back( que[niv][j][k] );
else menor.push_back( que[niv][j][k] );
}
l[nxt].push_back(mid); r[nxt].push_back(r[niv][j]); que[nxt].push_back(maior);
if(mid-1 >= l[niv][j]){ l[nxt].push_back(l[niv][j]); r[nxt].push_back(mid-1); que[nxt].push_back(menor); }
}
l[niv].clear(); r[niv].clear(); que[niv].clear();
niv = nxt;
}
for(int i = 0; i < sz(l[niv]); i++)
for(int j = 0; j < sz(que[niv][i]); j++) ans[ que[niv][i][j] ] = l[niv][i];
for(int i = 1; i <= q; i ++)cout<<ans[i]<<"\n";
}
