#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
struct node {
i64 val;
node *l, *r;
node() : val(0), l(nullptr), r(nullptr) {}
node(i64 x) : val(x), l(nullptr), r(nullptr) {}
node(node *L, node *R) : val(L->val + R->val), l(L), r(R) {}
node(node *x) : val(x->val), l(x->l), r(x->r) {}
};
constexpr int maxN = int(2E5) + 5;
int A[maxN];
node* roots[maxN];
node* build(int l, int r) {
if(l == r) {
return new node();
}
int mid = (l + r) >> 1;
return new node(build(l, mid), build(mid + 1, r));
}
node* modify(node *v, int l, int r, int p) {
if(l == r) {
return new node(v->val + 1);
}
int mid = (l + r) >> 1;
if(p <= mid) {
return new node(modify(v->l, l, mid, p), v->r);
}
return new node(v->l, modify(v->r, mid + 1, r, p));
}
i64 query(node *vl, node *vr, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return vr->val - vl->val;
} else if(r < ql || qr < l) {
return 0;
}
int mid = (l + r) >> 1;
return query(vl->l, vr->l, l, mid, ql, qr)
+ query(vl->r, vr->r, mid + 1, r, ql, qr);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, Q;
std::cin >> N >> Q;
roots[0] = build(1, maxN);
for(int i = 1; i <= N; ++i) {
std::cin >> A[i];
roots[i] = modify(roots[i - 1], 1, maxN, A[i]);
}
while(Q--) {
int L, R;
std::cin >> L >> R;
int lo = 0, hi = R - L + 1;
while(lo < hi) {
int mid = (lo + hi + 1) >> 1;
debug(query(roots[L - 1], roots[R], 1, maxN, mid, maxN));
if(query(roots[L - 1], roots[R], 1, maxN, mid, maxN) >= mid) {
lo = mid;
} else {
hi = mid - 1;
}
}
std::cout << lo << '\n';
}
return 0;
}
