#include <bits/stdc++.h>
using namespace std;
const int B = 500;
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int _n) {
n = _n;
tree.resize(n+5, 0);
}
void update(int x) {
for (; x <= n; x += x & -x)
tree[x] ++;
}
int get(int x) {
int res = 0;
for (; x; x -= x & -x)
res += tree[x];
return res;
}
};
int n, q;
pair<int, int> a[200005];
int l[200005], r[200005];
int lo[200005], hi[200005];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++ i) {
cin >> a[i].first;
a[i].second = i;
}
for (int i = 1; i <= q; ++ i) {
cin >> l[i] >> r[i];
lo[i] = 0, hi[i] = n + 1;
}
sort(a + 1, a + 1 + n);
int rem = q;
for (;;) {
vector<pair<int, int>> mid(rem);
for (int i = 1, cnt = 0; i <= q; ++ i)
if (hi[i] - lo[i] > 1) {
int cur = (lo[i] + hi[i]) >> 1;
mid[cnt++] = {cur, i};
}
sort(mid.begin(), mid.end());
reverse(mid.begin(), mid.end());
FenwickTree ft(n);
int run = n;
for (auto& pii : mid) {
while (run >= 1 && a[run].first >= pii.first) {
ft.update(a[run].second);
-- run;
}
int u = pii.second;
int cur = ft.get(r[u]) - ft.get(l[u]-1);
if (cur >= pii.first)
lo[u] = pii.first;
else
hi[u] = pii.first;
if (hi[u] - lo[u] == 1) -- rem;
}
if (rem == 0) break;
}
for (int i = 1; i <= q; ++ i)
cout << lo[i] << "\n";
return 0;
}
