#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl
#define left __left
#define right __right
#define prev __prev
#define fi first
#define se second
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
int n, q;
#define MAX_N 200'200
int a[MAX_N + 2];
struct Query {
int l, r;
void input() {
cin >> l >> r;
}
} query[MAX_N + 2];
namespace subtask1 {
bool check() {
return (n <= int(1e4));
}
struct MST {
vector <int> seg[4 * MAX_N + 2];
vector <int> Merge(const vector <int> &a, const vector <int> &b) {
vector <int> res;
int i = 0, j = 0;
while (i < SZ(a) && j < SZ(b)) {
if (a[i] <= b[j]) {
res.push_back(a[i++]);
} else {
res.push_back(b[j++]);
}
}
while (i < SZ(a)) res.push_back(a[i++]);
while (j < SZ(b)) res.push_back(b[j++]);
return res;
}
void build(int id, int l, int r) {
if (l == r) {
seg[id].push_back(a[l]);
return;
}
int g = (l + r) >> 1;
build(id << 1, l, g);
build(id << 1 | 1, g + 1, r);
seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v, const int &value) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) {
int lef = 0, rig = SZ(seg[id]) - 1, g, vt = -1;
while (lef <= rig) {
g = (lef + rig) >> 1;
if (seg[id][g] >= value) vt = g, rig = g - 1;
else lef = g + 1;
}
if (vt == -1) return 0;
return SZ(seg[id]) - vt;
}
int g = (l + r) >> 1;
return get(id << 1, l, g, u, v, value) + get(id << 1 | 1, g + 1, r, u, v, value);
}
} st;
void solve() {
st.build(1, 1, n);
while (q--) {
int L, R;
cin >> L >> R;
int l = 1, r = R - L + 1, g, vt = -1;
while (l <= r) {
g = (l + r) >> 1;
if (st.get(1, 1, n, L, R, g) >= g) vt = g, l = g + 1;
else r = g - 1;
}
if (vt == -1) vt = 0;
cout << vt << "\n";
}
}
};
namespace subtask2 {
int ans[MAX_N + 2];
int l[MAX_N + 2], r[MAX_N + 2], value[MAX_N + 2];
vector <pair <int, int>> queries[MAX_N + 2];
struct BIT {
int bit[MAX_N + 2];
int lim;
void init(int _n) {
lim = _n + 1;
FOR(i, 1, _n + 1) bit[i] = 0;
}
void update(int x, int v) {
for (; x <= lim; x += x & (-x)) bit[x] += v;
}
int get(int x) {
int ans = 0;
for (; x > 0; x -= x & (-x)) ans += bit[x];
return ans;
}
int calc(int l, int r) {
if (l > r) return 0;
return get(r) - get(l - 1);
}
} fen;
vector <bool> calc(const vector <int> &vec) {
int lim = *max_element(a + 1, a + 1 + n) + 2;
FOR(i, 0, n) queries[i].clear(), value[i] = 0;
fen.init(lim);
// build query;
for (int id : vec) {
queries[ query[id].l - 1 ].push_back({id, -1});
queries[ query[id].r ].push_back({id, 1});
}
FOR(i, 1, n) {
fen.update(a[i], 1);
for (auto it : queries[i]) {
int id = it.fi, mul = it.se;
int mid = (l[id] + r[id]) >> 1;
value[id] += mul * fen.calc(mid, lim);
}
}
vector <bool> res;
for (int id : vec) {
int mid = (l[id] + r[id]) >> 1;
res.push_back(value[id] >= mid);
}
return res;
}
void solve() {
FOR(i, 1, q) query[i].input();
FOR(i, 1, q) ans[i] = -1;
vector <int> checks;
FOR(i, 1, q) {
checks.push_back(i);
l[i] = 1, r[i] = query[i].r - query[i].l + 1;
}
while (true) {
vector <bool> results = calc(checks);
vector <int> tmp;
for (int i = 0; i < SZ(checks); ++i) {
int id = checks[i], mid = (l[id] + r[id]) >> 1;
if (results[i]) ans[id] = mid, l[id] = mid + 1;
else r[id] = mid - 1;
if (l[id] <= r[id]) tmp.push_back(id);
}
checks = tmp;
if (checks.empty()) break;
}
FOR(i, 1, q) cout << (~ans[i] ? ans[i] : 0) << "\n";
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
if (fopen("test.inp","r")) {
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
cin >> n >> q;
FOR(i, 1, n) cin >> a[i];
// if (subtask1 :: check()) return subtask1 :: solve(), 0;
subtask2 :: solve();
return 0;
}
/* Discipline - Calm */
