#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;
}
