#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), all, nxt(2e5, 0), pr(2e5); for (int i = 2e5; i; i--) { if (pos[i].size()) { all.push_back(i); } } for (int i = 0; i < all.size() - 1; i++) { nxt[all[i]] = all[i + 1]; } for (int i = 1; i < all.size(); i++) { pr[all[i]] = all[i - 1]; } pr[all[0]] = 1e9; pr[0] = all.back(); iota(init.begin(), init.end(), 0); bs.push({1, 2e5, init}); int cur = all[0]; FenwickTree fwt(n); while (bs.size()) { auto [l, r, v] = bs.front(); bs.pop(); if (r - l <= 2) { if (pr[cur] < r) { fwt = FenwickTree(n); cur = all[0]; } while (cur >= r) { for (auto &i : pos[cur]) { fwt.update(i); } cur = nxt[cur]; } for (auto &i : v) { 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 = nxt[cur]; } for (auto &i : v) { 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 = nxt[cur]; } for (auto &i : v) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= l) { ans[i] = max(ans[i], l); } } } else { int m = (l + r) / 2; if (pr[cur] < m) { fwt = FenwickTree(n); cur = all[0]; } while (cur >= m) { for (auto &i : pos[cur]) { fwt.update(i); } cur = nxt[cur]; } vector<int> vl, vr; for (auto &i : v) { auto &[lb, rb] = queries[i]; if (fwt.query(lb, rb) >= m) { vr.push_back(i); } else { vl.push_back(i); } } bs.push({m, r, vr}); bs.push({l, m - 1, vl}); } } for (auto &i : ans) { cout << i << "\n"; } return 0; }