#include <bits/stdc++.h>
#define kien long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define task "a"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pii pair <int, int>
using namespace std;
//const int LOG = 18;
const int mxn = 2e5 + 5;
kien n, lb[mxn], rb[mxn], ans[mxn], l[mxn], r[mxn];
vector <int> vec[mxn];
pii a[mxn];
struct FenwickTree {
int N;
kien bit[mxn];
void init(int n) {
N = n;
for (int i = 1; i <= N; i++) bit[i] = 0;
}
void update(int pos, int val) {
for (; pos <= N; pos += pos & -pos) bit[pos] += val;
}
kien get(int pos) {
kien s = 0;
for (; pos > 0; pos -= pos & -pos) s += bit[pos];
return s;
}
void update_range(int u, int v, int val) {
update(u, val);
update(v + 1, -val);
}
} BIT;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r")) {
fin(task); fou(task);
}
kien q;
cin >> n >> q;
FOR (i, 1, n) cin >> a[i].first, a[i].second = i;
sort (a + 1, a + 1 + n);
FOR (i, 1, q) {
cin >> l[i] >> r[i];
lb[i] = 1, rb[i] = r[i] - l[i] + 1;
}
/// log. q + log. n. log + n. log
int LOG = 19;
while (LOG--) {
vector <int> datas;
FOR (i, 1, q) {
if (lb[i] > rb[i]) continue;
int mid = (lb[i] + rb[i]) >> 1;
if (vec[mid].empty()) datas.pb(mid);
vec[mid].pb(i);
}
sort (datas.begin(), datas.end(), greater<int>());
int i = n;
BIT.init(n + 1);
for (auto x : datas) {
while (a[i].first >= x and i >= 1) {
BIT.update(a[i].second, 1);
i--;
}
for (auto v : vec[x]) {
// cout <<
// if (v == 6) cout << BIT.get(r[v]) - BIT.get(l[v] - 1) << " " << x << "\n";
if (BIT.get(r[v]) - BIT.get(l[v] - 1) >= x) {
lb[v] = x + 1;
ans[v] = x;
}
else rb[v] = x - 1;
}
vec[x].clear();
}
}
FOR (i, 1, q) cout << ans[i] << "\n";
}
