#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define int long long #define PI pair<int,int> #define f first #define s second #define pb push_back #define szo(x) ((int)x.size()) const int MAX = 2e7; int seg[MAX]; int L[MAX], R[MAX]; int nodes = 1; const int LIM = 2e5+10; void build(int x = 1, int l = 0, int r = LIM){ if (l == r) return; int tm = (l+r)/2; L[x] = nodes++, R[x] = nodes++; build(L[x], l, tm); build(R[x], tm+1, r); } int update(int id, int val, int x, int xo, int l = 0, int r = LIM){ if (l == r) return seg[x] = seg[xo]+val; int tm = (l+r)/2; if (id <= tm) return seg[x] = update(id, val, L[x] = nodes++, L[xo], l, tm) + seg[R[x] = R[xo]]; return seg[x] = update(id, val, R[x] = nodes++, R[xo], tm+1, r) + seg[L[x] = L[xo]]; } int solve(int r1, int r2, int acc, int l = 0, int r = LIM){ if (l == r) return l; int tm = (l+r)/2; if (acc + seg[R[r1]] - seg[R[r2]] >= tm+1) return solve(R[r1], R[r2], acc, tm+1, r); return solve(L[r1], L[r2], acc+seg[R[r1]]-seg[R[r2]], l, tm); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,q; cin >> n >> q; vector<int> vec(n+1); for (int i = 1; i <= n; ++i) cin >> vec[i]; build(); vector<int> rts(n+1); rts[0] = 0; for (int i = 1; i <= n; ++i){ rts[i] = nodes++; update(vec[i], 1, rts[i], rts[i-1]); } while (q--){ int l, r; cin >> l >> r; cout << solve(rts[r], rts[l-1], 0) << '\n'; } return 0; }