#include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll int64_t #define ull uint64t #define show(v) cout << #v ": " << (v) << endl #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f using namespace std; #define MAX 200010 #define UPD MAX #define LOG 19 #define MAXS (2*MAX + UPD*LOG * 2) namespace perseg { int seg[MAXS]; int rt[MAX], L[MAXS], R[MAXS]; int cnt = 0; void build(int p, int l, int r) { if (l == r) return; L[p] = cnt++; R[p] = cnt++; int m = (l + r) / 2; build(L[p], l, m); build(R[p], m + 1, r); } int update(int x, int lp, int p, int l, int r) { if (l == r) return seg[p] = seg[lp] + 1; int m = (l + r) / 2; if (x <= m) { R[p] = R[lp]; return seg[p] = update(x, L[lp], L[p] = cnt++, l, m) + seg[R[p]]; } else { L[p] = L[lp]; return seg[p] = seg[L[p]] + update(x, R[lp], R[p] = cnt++, m + 1, r); } } int query(int lp, int rp, int l, int r, int acc) { if (l == r) return l; int m = (l + r) / 2; int cntr = seg[R[rp]] - seg[R[lp]]; if (cntr + acc >= m + 1) { return query(R[lp], R[rp], m + 1, r, acc); } else { return query(L[lp], L[rp], l, m, acc + cntr); } } } int n, q; int p[MAX]; void solve() { cin >> n >> q; perseg::rt[0] = perseg::cnt++; perseg::build(perseg::rt[0], 0, n); for(int i = 0; i < n; i++) { cin >> p[i]; p[i] = min(p[i], n); perseg::rt[i+1] = perseg::cnt++; perseg::update(p[i], perseg::rt[i], perseg::rt[i+1], 0, n); } while (q--) { int l, r; cin >> l >> r; cout << perseg::query(perseg::rt[l-1], perseg::rt[r], 0, n, 0) << '\n'; } } int main() { int ttt = 1; // cin >> ttt; while(ttt--) { solve(); } return 0; }