#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n,q;
ll a[N], res[N], L[N], R[N], tot[N];
vector<ll>t[N];
struct fenwick_tree{
ll n;
vector<ll>ft;
void init(ll _n){
n = _n;
ft.clear(); ft.resize(n + 10);
}
void update(ll idx, ll val){
while(idx <= n) ft[idx] += val, idx += (idx & (-idx));
}
ll get(ll idx){
ll res = 0;
while(idx > 0) res += ft[idx], idx -= (idx & (-idx));
return res;
}
} ft;
void para_bs(){
ft.init(2e5);
for(int i = 1; i <= q;i++) tot[i] = 0;
for(int i = 1; i <= n;i++){
ft.update(a[i], 1);
for(auto x : t[i]){
ll j = abs(x);
if(L[j] > R[j]) continue;
ll mid = (L[j] + R[j]) / 2;
if(x < 0) tot[j] -= ft.get(2e5) - ft.get(mid - 1);
else{
if(L[j] > R[j]) continue;
tot[j] += ft.get(2e5) - ft.get(mid - 1);
if(tot[j] >= mid){
res[j] = mid;
L[j] = mid + 1;
}
else R[j] = mid - 1;
}
}
}
}
void to_thic_cau(){
cin >> n >> q;
for(int i = 1; i <= n;i++) cin >> a[i];
for(int i = 1; i <= q;i++){
ll l,r; cin >> l >> r;
t[r].pb(i); t[l - 1].pb(-i);
L[i] = 1, R[i] = 2e5;
}
for(int i = 1; i <= 20;i++) para_bs();
for(int i = 1; i <= q;i++) cout << res[i] << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
