#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
struct Node {
Node *l, *r;
int sum = 0;
Node(Node *left, Node *right) : l(left), r(right) {
if (l) sum += l->sum;
if (r) sum += r->sum;
}
Node(int s) : sum(s) {}
};
Node *build(int tl, int tr) {
if (tl == tr) {
return new Node(0);
} else {
int tm = (tl + tr) / 2;
return new Node(build(tl, tm), build(tm+1, tr));
}
}
Node *upd(Node *v, int tl, int tr, int pos) {
if (tl == tr) {
return new Node(v->sum+1);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
return new Node(upd(v->l, tl, tm, pos), v->r);
} else {
return new Node(v->l, upd(v->r, tm+1, tr, pos));
}
}
}
int qry(Node *v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) {
return v->sum;
} else {
int tm = (tl + tr) / 2;
return qry(v->l, tl, tm, l, min(tm, r)) + qry(v->r, tm+1, tr, max(tm+1, l), r);
}
}
const int MAXV = 200001;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<Node *> roots = {build(1, MAXV)};
for (int i = 1; i <= n; i++) {
int x; cin >> x;
roots.push_back(upd(roots.back(), 1, MAXV, x));
}
while (q--) {
int l, r; cin >> l >> r;
int lo = 1, hi = r-l+1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int cnt = qry(roots[r], 1, MAXV, mid, MAXV) - qry(roots[l-1], 1, MAXV, mid, MAXV);
if (cnt >= mid) {
lo = mid;
} else {
hi = mid - 1;
}
}
cout << lo << "\n";
}
}
