#include <bits/stdc++.h> using namespace std; #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' typedef long long ll; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; int n, q; const int MAXN = 400000 + 10; const int MAXQ = 400000; namespace perseg { const int LOGQ = 20; const int MAX = 2*MAXN + LOGQ*MAXQ; int sz = 0; int n; int sum[MAX], L[MAX], R[MAX]; void build(int p, int l, int r) { sum[p] = 0; if (l == r) { return; } L[p] = sz++; R[p] = sz++; int mid = (l + r) / 2; build(L[p], l, mid); build(R[p], mid + 1, r); } void build(int n_) { n = n_; build(0, 0, n); } int query(int lr, int rr, int l = 0, int r = n, ll adj = 0) { // check if current is ok (base case) if (sum[rr] - sum[lr] + adj < l) return -1; if (l == r) return l; // check right int mid = (l + r) / 2; // cerr << mid + 1 << ' ' << n << ' ' ; // cerr << sum[R[rr]] - sum[R[lr]] + adj << endl; if (sum[R[rr]] - sum[R[lr]] + adj >= mid + 1) { return query(R[lr], R[rr], mid + 1, r, adj); } else { return query(L[lr], L[rr], l, mid, sum[R[rr]] - sum[R[lr]] + adj); } } int update(int p, int& np, int l, int r, int i, int x) { if (i < l or r < i) { np = p; return sum[p]; } np = sz++; if (l == r and l == i) { sum[np] = sum[p] + x; return sum[np]; } int mid = (l + r) / 2; sum[np] = update(L[p], L[np], l, mid, i, x); sum[np] += update(R[p], R[np], mid + 1, r, i, x); return sum[np]; } int update(int r, int i, int x) { int nr = r; update(r, nr, 0, n, i, x); return nr; } } int roots[MAXQ]; int main() {_; cin >> n >> q; perseg::build(n); roots[0] = 0; for (int i = 1; i <= n; i++) { int p; cin >> p; roots[i] = perseg::update(roots[i-1], p, 1); } while (q--) { int l, r; cin >> l >> r; int ans = perseg::query(roots[l-1], roots[r]); assert(ans != -1); cout << ans << endl; } return 0; }