#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
const int N = 2e5 + 69;
const int M = 17 * N;
int n, q, a[N];
int st[M], root[N], lc[M], rc[M], node;
vector<int> pos[N];
void modify(int v, int rt, int tl, int tr, int p) {
if (tl == tr)
st[v] = 1;
else {
int mid = (tl + tr) / 2;
if (p <= mid) {
lc[v] = ++node;
rc[v] = rc[rt];
modify(lc[v], lc[rt], tl, mid, p);
}
else {
rc[v] = ++node;
lc[v] = lc[rt];
modify(rc[v], rc[rt], mid + 1, tr, p);
}
st[v] = st[lc[v]] + st[rc[v]];
}
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
else if (tl >= l && tr <= r)
return st[v];
else {
int mid = (tl + tr) / 2;
return get(lc[v], tl, mid, l, r) + get(rc[v], mid + 1, tr, l, r);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
//freopen("newbarn.in", "r", stdin);
//freopen(newbarn.out", "w", stdout);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> q;
for (int i = 1;i <= n;i++) {
cin >> a[i];
pos[a[i]].push_back(i);
}
for (int i = N - 1;i >= 1;i--) {
root[i] = root[i + 1];
for (auto u : pos[i]) {
int nr = ++node;
modify(nr, root[i], 1, n, u);
root[i] = nr;
}
}
while (q--) {
int x, y;
cin >> x >> y;
int l = 1, r = N - 1, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
int g = get(root[mid], 1, n, x, y);
if (g >= mid) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans << '\n';
}
}
return 0;
}
