#include <bits/stdc++.h>
using namespace std;
#define md ((l + r) >> 1)
struct node {
int l, r, v;
node() {l = 0, r = 0, v = 0;}
node(int _v) {l = 0, r = 0, v = _v;}
} seg[4'000'005];
int cur = 2;
int newpar(int l, int r) {
int i = cur++;
seg[i].l = l;
seg[i].r = r;
seg[i].v = seg[l].v + seg[r].v;
return i;
}
int newleaf(int v) {
int i = cur++;
seg[i] = node(v);
return i;
}
int upd(int i, int l, int r, int x, int v) {
if (l == r) {
return newleaf(seg[i].v + v);
}
if (x <= md) {
return newpar(upd(seg[i].l, l, md, x, v), seg[i].r);
} else {
return newpar(seg[i].l, upd(seg[i].r, md + 1, r, x, v));
}
}
int get(int rootl, int rootr, int l, int r, int k) {
if (k <= l) {
return seg[rootr].v - seg[rootl].v;
}
if (r < k) {
return 0;
}
return get(seg[rootl].l, seg[rootr].l, l, md, k) + get(seg[rootl].r, seg[rootr].r, md + 1, r, k);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
int a[n + 1], roots[n + 1];
roots[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
roots[i] = upd(roots[i - 1], 0, 200'000, a[i], 1);
}
while (q--) {
int s, e;
cin >> s >> e;
//0001111
int l = 0, r = e - s + 1;
while (l <= r) {
int h = ((l + r) >> 1);
if (get(roots[s - 1], roots[e], 0, 200'000, h) >= h) {
l = md + 1;
} else {
r = md - 1;
}
}
cout << r << '\n';
}
return 0;
}
