/* Author: goats_9 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 4e6;
constexpr int M = 2e5;
class persistent_segtree {
vector<int> f, l, r;
int n, nxt;
int update(int i, int x, int lx, int rx) {
int u = nxt++;
if (rx - lx == 1) {
f[u] = f[x] + 1;
return u;
}
l[u] = l[x], r[u] = r[x];
int m = (lx + rx) / 2;
if (i < m) l[u] = update(i, l[x], lx, m);
else r[u] = update(i, r[x], m, rx);
f[u] = f[l[u]] + f[r[u]];
return u;
}
int walk(int d, int a, int b, int lx, int rx) {
if (rx - lx == 1) return lx;
int m = (lx + rx) / 2;
int cnt_right = f[r[b]] - f[r[a]];
if (cnt_right + d >= m) return walk(d, r[a], r[b], m, rx);
return walk(d + cnt_right, l[a], l[b], lx, m);
}
public:
persistent_segtree(int _n) : f(N), l(N), r(N), n(_n), nxt(1) {}
int update(int i, int x) { return update(i, x, 0, n); }
int walk(int a, int b) { return walk(0, a, b, 0, n); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> p(n);
for (auto& u : p) cin >> u;
vector<int> roots(n + 1);
persistent_segtree pst(M + 1);
for (int i = 0; i < n; i++) roots[i + 1] = pst.update(p[i], roots[i]);
while (q--) {
int l, r;
cin >> l >> r;
cout << pst.walk(roots[--l], roots[r]) << '\n';
}
return 0;
}
