#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // https://codeforces.com/blog/entry/79148 class Timer: chrono::high_resolution_clock { const time_point start_time; public: Timer(): start_time(now()) {} rep elapsed_time() const { return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count(); } } timer; struct FenwickTree { int n; vector<int> tree; FenwickTree(int n_) { n = n_; tree.resize(n + 1, 0); } void update(int p) { while (p <= n) { tree[p]++; p += p & (-p); } } int prefixQuery(int r) { int res = 0; while (r) { res += tree[r]; r -= r & (-r); } return res; } int query(int l, int r) { return prefixQuery(r) - prefixQuery(l - 1); } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n, q; cin >> n >> q; vector<vector<int>> pos(2e5 + 1); for (int i = 1; i <= n; i++) { int x; cin >> x; pos[x].push_back(i); } vector<pair<int, int>> queries(q); for (int i = 0; i < q; i++) { cin >> queries[i].first >> queries[i].second; } queue<tuple<int, int, vector<int>>> bs; vector<int> init(q), ans(q, 0); iota(init.begin(), init.end(), 0); bs.push({1, 2e5, init}); int cur = 2e5; FenwickTree fwt(n); while (bs.size()) { auto [l, r, v] = bs.front(); bs.pop(); if (r - l <= 2) { if (cur < r - 1) { fwt = FenwickTree(n); cur = 2e5; } while (cur >= r) { for (auto &i : pos[cur]) { fwt.update(i); } cur--; } for (int i = 0; i < q; i++) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= r) { ans[i] = max(ans[i], r); } } while (cur >= l + 1) { for (auto &i : pos[cur]) { fwt.update(i); } cur--; } for (int i = 0; i < q; i++) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= l + 1) { ans[i] = max(ans[i], l + 1); } } while (cur >= l) { for (auto &i : pos[cur]) { fwt.update(i); } cur--; } for (int i = 0; i < q; i++) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= l) { ans[i] = max(ans[i], l); } } } else { int m = (l + r) / 2; if (cur < m - 1) { fwt = FenwickTree(n); cur = 2e5; } while (cur >= m) { for (auto &i : pos[cur]) { fwt.update(i); } cur--; } vector<int> vl, vr; for (int i = 0; i < q; i++) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= m) { vr.push_back(i); } else { vl.push_back(i); } } bs.push({m + 1, r, vr}); bs.push({l, m, vl}); } } for (auto &i : ans) { cout << i << "\n"; } return 0; }