#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll INF = 2e18;
ll n, q;
struct qt{
ll l, r;
vector<ll> v;
};
ll p[200005];
pll qs[200005];
ll ans[200005];
ll fw[200005];
void update(int x, ll v){ //x CANNOT BE 0, fenwick is 1-indexed
for (; x<=n; x+=x&(-x)) fw[x] += v;
}
ll sum(int x){
ll res = 0;
for(; x; x-=x&(-x)) res += fw[x];
return res;
}
ll r_sum(int l, int r){ return sum(r)-sum(l-1); }
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
vector<pll> v; v.push_back({-INF, -INF});
for (int i=1; i<=n; i++) cin >> p[i], v.push_back({p[i], i});
for (int i=1; i<=q; i++) cin >> qs[i].first >> qs[i].second;
sort(v.begin(), v.end());
queue<qt> que;
vector<ll> t; for (int i=1; i<=q; i++) t.push_back(i);
qt fi = {1, n, t}; que.push(fi); //fi stores {min_ans, max_ans, indexes of queries}
ll ptr = n; //index for last split
while (!que.empty()){
auto [lo, hi, cv] = que.front(); que.pop();
ll md = (lo+hi)>>1;
if (lo+1 >= hi){
for (auto x : cv) ans[x] = hi;
continue;
}
else{
if (v[ptr].first < md){
memset(fw, 0, sizeof(fw));
ptr = n;
}
while (ptr >= 1 && v[ptr].first >= md){
update(v[ptr].second, 1);
ptr--;
}
vector<ll> l, r;
for (auto u : cv){
auto [ql, qr] = qs[u];
ll val = r_sum(ql, qr);
if (val >= md) r.push_back(u);
else l.push_back(u);
}
if (!r.empty()) que.push({md, hi, r});
if (!l.empty()) que.push({lo, md, l});
}
}
for (int i=1; i<=q; i++) cout << --ans[i] << "\n";
return 0;
}
