#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int M=1<<20;
int n,h[N];
struct UWU{
vector<pair<int,int>> s;
vector<int> arr;
void init(){
s.resize(M,{0,0}),arr.resize(M,0);
}
void build(int l,int r,int idx){
if(l==r){
s[idx]={arr[l],-l};
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
pair<int,int> query(int l,int r,int idx,int a,int b){
if(a>r || b<l) return {INT_MIN,0};
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
int ask(int l,int r){
pair<int,int> tmp=query(1,n,1,l,r);
return -tmp.second;
}
}T;
vector<tuple<int,int,int>> qr[N];
int ret[N];
tuple<vector<int>,vector<int>,int> solve(int l,int r){
//solve on [l,mx-1] and [mx+1,r];
if(l>r){return {{},{},0};}
vector<int> mxi;
int bl=l;
//cout<<"vs" <<l <<" " <<r <<"\n";
while(bl<=r){
int cd=T.ask(bl,r);
if(mxi.empty()) mxi.push_back(cd);
else{
if(h[cd]==h[mxi.back()]) mxi.push_back(cd);
else{
break;
}
}
bl=cd+1;
}
//for(auto x:mxi) cout<<x <<" ";
//cout<<"\n";
int now=l;
int sz=mxi.size();
vector<int> rpre,rsuf;
for(int i=0;i<=sz;i++){
auto [vpre,vsuf,m0]=solve(i==0?l:mxi[i-1]+1,i==sz?r:mxi[i]-1);
//convert vpre and vpos from m0 to h[mxi[0]]
//cout<<"i" <<i <<" " <<(i==0?l:mxi[i-1]+1) <<" " <<(i==sz?r:mxi[i]-1) <<"\n";
int exp=h[mxi[0]]-m0;
if(exp>=20){
if(!vpre.empty()) vpre={vpre.back()};
if(!vsuf.empty()) vsuf={vsuf[0]};
}
else{
int comp=1<<exp;
int cnt=0;
vector<int> vp,vs;
for(int i=0;i<vpre.size();i++){
cnt++;
if(cnt==comp){
cnt=0;
vp.push_back(vpre[i]);
continue;
}
if(i==(int)vpre.size()-1) vp.push_back(vpre[i]);
}
cnt=0;
for(int i=(int)vsuf.size()-1;i>=0;i--){
cnt++;
if(cnt==comp){
cnt=0;
vs.push_back(vsuf[i]);
continue;
}
if(i==0) vs.push_back(vsuf[i]);
}
reverse(vs.begin(),vs.end());
vpre=vp,vsuf=vs;
}
// for(auto x:vpre) cout<<x <<" ";
// cout<<"\n";
// for(auto x:vsuf) cout<<x <<" ";
// cout<<"\n";
for(auto x:vpre) rpre.push_back(x);
for(auto x:vsuf) rsuf.push_back(x);
if(i!=sz) rpre.push_back(mxi[i]),rsuf.push_back(mxi[i]);
}
for(int i=0;i<sz;i++){
//answer query using pre,suf
for(auto [l,r,id]:qr[mxi[i]]){
int cl=lower_bound(rsuf.begin(),rsuf.end(),mxi[i])-(upper_bound(rsuf.begin(),rsuf.end(),l)-1);
int cr=lower_bound(rpre.begin(),rpre.end(),r)-lower_bound(rpre.begin(),rpre.end(),mxi[i]);
ret[id]=h[mxi[i]]+(int)ceil(log2(cl+cr+1));
}
}
// cout<<"solve" <<l <<" " <<r <<"\n";
// for(auto x:rpre) cout<<x <<" ";
// cout<<"\n";
// for(auto x:rsuf) cout<<x <<" ";
// cout<<"\n";
return {rpre,rsuf,h[mxi[0]]};
}
int main(){
T.init();
int q; cin>>n >>q;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) T.arr[i]=h[i];
T.build(1,n,1);
for(int i=0;i<q;i++){
int l,r; cin>>l >>r;
int id=T.ask(l,r);
qr[id].push_back({l,r,i});
}
solve(1,n);
for(int i=0;i<q;i++){
cout<<ret[i] <<"\n";
}
}
