#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], f;
segtree(){
f = new node(0);
f->l = f->r = f;
}
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, int l, int r, int L, int R){
if(r < L || l > R || !k) return 0;
if(l == r) return k->v;
int md = (l + r) / 2;
return qry(k->l, l, md, L, R) + qry(k->r, md + 1, r, L, R);
}
}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, x);
}
while(q--){
int l, r;
cin >> l >> r;
int L = 1, R = n, ans = -1;
while(L <= R){
int md = (L + R) / 2;
if(s.qry(s.rt[r], 1, n, md, n) - s.qry(s.rt[l - 1], 1, n, md, n) >= md){
ans = md;
L = md + 1;
}else{
R = md - 1;
}
}
cout << ans << '\n';
}
}
