#include <bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;
struct segtree{
struct node{
int v;
node *l, *r;
node(int v) : v(v), l(0), r(0){}
};
typedef node* pnode;
pnode rt[N];
void build(pnode &k, int l, int r){
k = new node(0);
int md = (l + r) / 2;
if(l == r) return;
build(k->l, l, md);
build(k->r, md + 1, r);
}
void upd(pnode &k, pnode pv, int l, int r, int idx){
k = new node(*pv);
if(l == r) return k->v += 1, void();
int md = (l + r) / 2;
if(idx <= md) upd(k->l, pv->l, l, md, idx);
else upd(k->r, pv->r, md + 1, r, idx);
k->v = (k->l ? k->l->v : 0) + (k->r ? k->r->v : 0);
}
int qry(pnode k, pnode q, int l, int r, int n, int pv){
if(l == r) return l;
int md = (l + r) / 2;
int lc = k->l->v - q->l->v;
if(lc + pv >= n - md + 1) return qry(k->l, q->l, l, md, n, pv);
else return qry(k->r, q->r, md + 1, r, n, pv + lc);
}
}s;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
s.build(s.rt[0], 1, n);
for(int i = 1;i<=n;i++){
int x;
cin >> x;
s.upd(s.rt[i], s.rt[i - 1], 1, n, n - x + 1);
}
while(q--){
int l, r;
cin >> l >> r;
cout << n - s.qry(s.rt[r], s.rt[l - 1], 1, n, n, 0) + 1 << '\n';
}
}
