#include <bits/stdc++.h>
using namespace std;
int N;
const int MAX = 2e5 + 10;
vector<int> tree[2 * MAX];
int query(int l, int r, int v) {
int S = 0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
S += tree[l].end() - lower_bound(tree[l].begin(), tree[l].end(), v);
l++;
}
if (r & 1) {
r--;
S += tree[r].end() - lower_bound(tree[r].begin(), tree[r].end(), v);
}
}
return S;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int Q, L, R, l, r, m, ans, P;
cin >> N >> Q;
for (int i = 0; i < N; i++) {
cin >> P;
tree[N + i].push_back(P);
}
for (int i = N - 1; i > 0; i--) {
vector<int>& lv = tree[(i << 1)];
vector<int>& rv = tree[(i << 1) | 1];
tree[i].resize(lv.size() + rv.size());
auto lp = lv.begin(), rp = rv.begin(), it = tree[i].begin();
while (lp != lv.end() && rp != rv.end()) *(it++) = *((*lp < *rp ? lp : rp)++);
while (lp != lv.end()) *(it++) = *(lp++);
while (rp != rv.end()) *(it++) = *(rp++);
}
while (Q--) {
cin >> L >> R;
l = 1, r = R - L + 1, L--;
while (l <= r) {
m = (l + r) >> 1;
if (query(L, R, m) >= m) {
ans = m;
l = ++m;
} else {
r = --m;
}
}
cout << ans << '\n';
}
}
