#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
const int maxn = 200'001;
const int N = 1 << (__lg(maxn) + 1);
int l[maxn], r[maxn], la[maxn], ra[maxn], ans[maxn];
vector<int> pos[maxn], buckets[maxn];
// pos[i] = all indices j which have p[j] = i
int seg[2 * N];
void update (int i) {
i = i + N - 1;
seg[i] = 1;
while (i /= 2) seg[i] = seg[i * 2] + seg[i * 2 + 1];
}
int query (int ql, int qr, int i = 1, int l = 1, int r = N) {
if (l > qr || r < ql) return 0;
if (ql <= l && r <= qr) return seg[i];
int m = (l + r) / 2;
return query(ql, qr, i * 2, l, m) + query(ql, qr, i * 2 + 1, m + 1, r);
}
signed main () {
cin.tie(0) -> sync_with_stdio(0);
int n, q; cin >> n >> q;
int p[n + 1];
for (int i = 1 ; i <= n ; i++) {
cin >> p[i];
pos[p[i]].push_back(i);
}
for (int i = 1 ; i <= q ; i++) {
cin >> l[i] >> r[i];
la[i] = 1, ra[i] = n;
buckets[(1 + n) / 2].push_back(i);
}
for (int _ = 0 ; _ <= __lg(maxn) ; _++) {
memset(seg, 0, sizeof seg);
for (int i = maxn - 1 ; i >= 0 ; i--) {
for (int j : pos[i]) update(j);
// all values >= i have been inserted into 'os'
for (int j : buckets[i]) {
// count the number of k in 'os' such that l[j] <= k <= r[j]
int k = query(l[j], r[j]);
if (k >= i) {
ans[j] = i;
la[j] = i + 1;
} else {
ra[j] = i - 1;
}
if (la[j] <= ra[j]) {
buckets[(la[j] + ra[j]) / 2].push_back(j);
}
}
buckets[i].clear();
}
}
for (int i = 1 ; i <= q ; i++) cout << ans[i] << ' ';
}
