#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 2*1e5+5;
pair<int,int> o[MAXN];
vector<int> sum,e,d,rz;
int create(){
sum.push_back(0);
e.push_back(0);
d.push_back(0);
return sz(sum)-1;
}
int update(int node, int l, int r, int i){
int novo = create();
sum[novo] = sum[node];
e[novo] = e[node];
d[novo] = d[node];
if(l == r){
sum[novo]++;
return novo;
}
int mid = (l+r)/2;
if(i <= mid){
int aux = update(e[novo], l, mid, i);
e[novo] = aux;
}else{
int aux = update(d[novo], mid+1, r, i);
d[novo] = aux;
}
sum[novo] = sum[e[novo]]+sum[d[novo]];
return novo;
}
int query(int node, int l, int r, int i, int j){
if(node == 0 || j < l || r < i)return 0;
if(i <= l && r <= j)return sum[node];
int mid = (l+r)/2;
return query(e[node],l,mid,i,j) + query(d[node],mid+1,r,i,j);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q, mx; cin>>n>>q;
for(int i = 1; i <= n; i++){
int p; cin>>p;
mx = max(mx,p);
o[i] = {-p,i};
}
sort(o+1,o+1+n);
create(); rz.push_back(0); int pt = 1;
for(int i = mx; i >= 1; i--){
int nxt = rz.back();
while(pt <= n && -o[pt].fi == i){
int aux = update(nxt,1,n, o[i].sc);
nxt = aux;
pt++;
}
rz.push_back(nxt);
}
for(int i = 1; i <= q; i++){
int ini, fim; cin>>ini>>fim;
int l = 1, r = mx;
while(l != r){
int mid = (l+r+1)/2;
if(query(rz[mx-mid+1], 1, n, ini, fim) >= mid)l = mid;
else r = mid-1;
}
cout<<l<<"\n";
}
}
