#include <bits/stdc++.h>
using namespace std;
#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;
namespace perseg {
const int MAX = 2e6 + 10;
int n, seg[20 * MAX], l[20 * MAX], r[20 * MAX], at = 1, root;
int node(int cp=0) {
seg[at] = seg[cp], l[at] = l[cp], r[at] = r[cp];
return at++;
}
void build(int x, int lx, int rx) {
if (lx + 1 == rx) return;
int mid = (lx + rx) / 2;
build(l[x] = node(), lx, mid);
build(r[x] = node(), mid, rx);
}
void build(int _n) {
n = _n;
build(root = node(), 0, n);
}
void update(int i, int v, int x, int lx, int rx) {
if (lx + 1 == rx) {
seg[x] += v;
return;
}
int mid = (lx + rx) / 2;
if (i < mid) update(i, v, l[x] = node(l[x]), lx, mid);
else update(i, v, r[x] = node(r[x]), mid, rx);
seg[x] = seg[l[x]] + seg[r[x]];
}
int update(int i, int v) {
update(i, v, root = node(root), 0, n);
return root;
}
int solve(int r1, int r2, int cur=0, int lx=0, int rx=n) {
if (lx + 1 == rx) return lx;
int mid = (lx + rx) / 2;
int cntr = seg[r[r2]] - seg[r[r1]];
if (cur + cntr < mid) return solve(l[r1], l[r2], cur+cntr, lx, mid);
else return solve(r[r1], r[r2], cur, mid, rx);
}
}
int32_t main() {
fast_io;
int n, q; cin >> n >> q;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> roots(n + 1);
const int MAX = *max_element(a.begin(), a.end());
perseg::build(MAX + 1);
roots[0] = perseg::root;
for (int i = 0; i < n; i++) roots[i + 1] = perseg::update(a[i], 1);
while (q--) {
int l, r; cin >> l >> r;
cout << perseg::solve(roots[l - 1], roots[r]) << endl;
}
}
