#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> mat;
typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define lc 2*id
#define rc 2*id+1
#define pb push_back
#define all(x) x.begin(),x.end()
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define print(n) for(ll i:n){cout << i << ' ';}cout << endl;
ll pw(ll a,ll b,ll md=998244353){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}
const int maxn=5e5+50;
const ll mod=998244353;
const ll sq=330;
const ll lg=22;
const ll inf=2e18;
vector<ll> adj[maxn],add[maxn],ar[maxn];
int vis[maxn];
ll li[maxn],res[maxn],seg[4*maxn],a[maxn],b[maxn];
ll n,q;
vector<ll> vec;
set<ll> st;
void build(ll l,ll r,ll id){
if(l==r){
seg[id]=1;
return ;
}
ll mid=(l+r)/2;
build(l,mid,lc);
build(mid+1,r,rc);
seg[id]=seg[lc]+seg[rc];
}
void upd(ll l,ll r,ll p,ll id){
if(l>p || r<p)return ;
if(l==r){
seg[id]=0;
return ;
}
ll mid=(l+r)/2;
upd(l,mid,p,lc);
upd(mid+1,r,p,rc);
seg[id]=seg[lc]+seg[rc];
}
ll get(ll l,ll r,ll s,ll e,ll id){
if(l>e || r<s)return 0;
if(l>=s && r<=e)return seg[id];
ll mid=(l+r)/2;
return get(l,mid,s,e,lc)+get(mid+1,r,s,e,rc);
}
void solve(){
vec.clear();
for(ll i:st){
auto it=st.upper_bound(i);
if(it!=st.end()){
ll x=*it;
if(x-i>1)vec.pb((x+i)/2);
}
}
for(ll i:vec){
st.insert(i);
}
for(ll i=1;i<=q;i++){
ll x=*st.upper_bound(res[i]);
add[x].pb(i);
}
build(1,n,1);
for(ll i=1;i<=n;i++){
auto it=upper_bound(all(vec),li[i]);
if(it!=vec.end()){
ll x=*it;
ar[x].pb(i);
}
}
for(ll i:vec){
for(ll j:ar[i])upd(1,n,j,1);
for(ll j:add[i]){
if(get(1,n,a[j],b[j],1)>=i)res[j]=i;
}
}
}
int main(){
fast;
cin>>n>>q;
for(ll i=1;i<=n;i++){
cin>>li[i];
}
for(ll i=1;i<=q;i++){
cin>>a[i]>>b[i];
}
st.insert(0);st.insert(n+1);
for(ll i=1;i<=lg;i++){
solve();
}
for(ll i=1;i<=q;i++)cout<< res[i] << endl;
}
