#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
using ld = long double;
struct nd {
ll s, l, r;
};
vector<nd> t = {{0, -1, -1}};
void bld(ll v, ll l, ll r) {
if (l + 1 == r) {
t[v] = {0, -1, -1};
return;
}
ll md = (l + r) >> 1;
t.push_back({0, -1, -1});
t[v].l = t.size() - 1;
t.push_back({0, -1, -1});
t[v].r = t.size() - 1;
bld(t[v].l, l, md);
bld(t[v].r, md, r);
}
ll upd(ll v, ll l, ll r, ll i, ll x) {
//cout << v << ' ' << l << ' ' << r << endl;
ll nv = t.size();
t.push_back(t[v]);
if (l + 1 == r) {
t[nv] = {x, -1, -1};
return nv;
}
ll md = (l + r) >> 1;
if (i < md) t[nv].l = upd(t[v].l, l, md, i, x);
else t[nv].r = upd(t[v].r, md, r, i, x);
t[nv].s = t[t[nv].l].s + t[t[nv].r].s;
return nv;
}
ll get(ll v, ll l, ll r, ll ql, ll qr) {
if (l >= qr || ql >= r) return 0;
if (l >= ql && r <= qr) return t[v].s;
ll md = (l + r) >> 1;
return get(t[v].l, l, md, ql, qr) + get(t[v].r, md, r, ql, qr);
}
void solve() {
ll n, q;
cin >> n >> q;
vector<pair<ll, ll>> a(n);
for (ll i = 0; i < n; i++) cin >> a[i].first, a[i].second = i;
bld(0, 0, n);
vector<ll> pr(2e5 + 52);
sort(a.begin(), a.end());
ll last = 0;
for (ll i = n - 1; i > -1; i--) {
//cout << last << ' ' << a[i].second << endl;
ll cr = upd(last, 0, n, a[i].second, 1);
pr[a[i].first] = cr;
//cout << a[i].first << ' ' << cr << endl;
last = cr;
}
while (q--) {
ll l, r;
cin >> l >> r;
l--, r--;
ll lb = 1, rb = 2e5 + 1;
while (rb - lb > 1) {
ll md = (lb + rb) >> 1;
ll j = lower_bound(a.begin(), a.end(), make_pair(md, (ll)-1e18)) - a.begin();
if (j < a.size() && get(pr[a[j].first], 0, n, l, r + 1) >= md) lb = md;
else rb = md;
}
cout << lb << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
// cin >> t;
while (t--) {
solve();
}
}
