#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=2e5+10;
struct node{
int val;
node *l, *r;
node(): val(0), l(nullptr), r(nullptr) {}
node(int x): val(x), l(nullptr), r(nullptr) {}
node(node *ll, node *rr){
l=ll; r=rr;
val=0;
if(l) val+=l->val;
if(r) val+=r->val;
}
node(node *cp): val(cp->val), l(cp->l), r(cp->r) {} // tira copia
};
node *roots[maxn];
node *build(int ini, int fim){
if(ini==fim) return new node(0);
int mid=(ini+fim)/2;
return new node(build(ini,mid),build(mid+1,fim));
}
node *update(node *id, int ini, int fim, int cara){
// cerr << ini << ' ' << fim << '\n';
if(ini==fim) return new node(1);
int mid=(ini+fim)/2;
if(cara<=mid) return new node(update(id->l,ini,mid,cara),id->r);
else return new node(id->l,update(id->r,mid+1,fim,cara));
}
int query(node *id, int ini, int fim, int l, int r){
if(ini>r||fim<l) return 0;
if(l<=ini&&fim<=r) return id->val;
int mid=(ini+fim)/2;
return query(id->l,ini,mid,l,r)+query(id->r,mid+1,fim,l,r);
}
vector<int>caras[maxn];
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, q; cin >> n >> q;
for(int i=1;i<=n;i++){
int a; cin >> a;
caras[min(a,n)].push_back(i);
}
roots[0]=build(1,n);
for(int i=1;i<=n;i++){
// cerr << "! " << i << '\n';
roots[i]=new node(roots[i-1]);
for(int x : caras[i]) roots[i]=update(roots[i],1,n,x);
}
for(int i=1;i<=q;i++){
int a, b; cin >> a >> b;
int l=1, r=n;
while(l<r){
int mid=(l+r+1)/2;
if(query(roots[n],1,n,a,b)-query(roots[mid-1],1,n,a,b)>=mid) l=mid;
else r=mid-1;
}
cout << l << '\n';
}
}
