#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define int ll
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
// SegTree Persistente com Lazy
//
// Nao propaga, meio estranho de mexer, mas da
//
// query(a, b, t) retorna a query de [a, b] na versao t
// update(a, b, x, t) faz um update v[a..b]+=x a partir da
// versao de t, criando uma nova versao e retornando seu id
// Por default, faz o update a partir da ultima versao
//
// build - O(n)
// query - O(log(n))
// update - O(log(n))
const int MAX = 2e5+10, UPD = 2e5+10, LOG = 19;
const int MAXS = 2*MAX + 4*UPD*LOG;
namespace perseg {
int seg[MAXS], lazy[MAXS];
int rt[UPD], L[MAXS], R[MAXS], cnt, t;
int n, *v;
int build(int p, int l, int r) {
if (l == r) return seg[p] = v[l];
L[p] = cnt++, R[p] = cnt++;
int m = (l+r)/2;
return seg[p] = max(build(L[p], l, m), build(R[p], m+1, r));
}
void build(int n2, int *v2) {
n = n2, v = v2;
rt[0] = cnt++;
build(0, 0, n-1);
}
int query(int a, int b, int p, int l, int r) {
if (b < l or r < a) return -INF;
if (a <= l and r <= b) return lazy[p] + seg[p];
int m = (l+r)/2;
int ret = lazy[p] + max(query(a, b, L[p], l, m), query(a, b, R[p], m+1, r));
return ret;
}
int query(int a, int b, int tt) {
return query(a, b, rt[tt], 0, n-1);
}
int update(int a, int b, int x, int lp, int p, int l, int r) {
tie(seg[p], lazy[p], L[p], R[p]) = {seg[lp], lazy[lp], L[lp], R[lp]};
if (b < l or r < a) return seg[p] + lazy[p];
if (a <= l and r <= b) return seg[p] + (lazy[p] += x);
int m = (l+r)/2;
seg[p] = max(update(a, b, x, L[lp], L[p] = cnt++, l, m),
update(a, b, x, R[lp], R[p] = cnt++, m+1, r));
lazy[p] = lazy[lp];
return seg[p] + lazy[p];
}
int update(int a, int b, int x, int tt=t) {
assert(tt <= t);
update(a, b, x, rt[tt], rt[++t]=cnt++, 0, n-1);
return t;
}
};
void solve(){
int n, q; cin >> n >> q;
vector<int> v(n); for(int i = 0; i < n; i++) cin >> v[i];
int hist[MAX] = {0};
perseg::build(MAX, hist);
for(int i = 0; i < n; i++)
perseg::update(0, v[i], 1);
for(int i = 0; i < q; i++){
int a, b; cin >> a >> b; --a;
int l = 1, r = MAX, ans = l;
while(l <= r){
int m = l+(r-l)/2;
if(perseg::query(m, m, b)-perseg::query(m, m, a) >= m) ans = m, l = m+1;
else r = m-1;
}
cout << ans << endl;
}
}
int32_t main(){ _
int ttt = 1; // cin >> ttt;
while(ttt--) solve();
exit(0);
}
