#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<int> t;
int n;
void update(int p, int val){
for (t[p+=n] += val; p > 1; p/=2) t[p/2] = t[p] + t[p^1];
}
int query(int l, int r) {
r++;
int res = 0;
for (l += n, r += n; l < r; l/=2, r/=2) {
if (l&1) res += t[l++];
if (r&1) res += t[--r];
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int q; cin >> n >> q;
vector<int> h(n);
t.resize(2*n+4);
vector<pair<int,int>> sh;
for (int i = 0; i < n; i++) cin >> h[i];
for (int i = 0; i < n; i++) sh.push_back({h[i],i});
sort(rall(sh));
vector<pair<int,int>> que(q);
vector<int> ans(q);
for (int i = 0; i < q; i++) { cin >> que[i].first >> que[i].second; que[i].first--; que[i].second--; }
for (int i = 0; i < q; i++) cin >> que[i].first >> que[i].second;
vector<pair<pair<int,pair<int,int>>,int>> v;
for (int i = 0; i < q; i++) v.push_back({{(n+1)/2,{1,n}},i});
while(sz(v)>0){
vector<pair<pair<int,pair<int,int>>,int>> v2;
sort(rall(v));
for (int i = 0; i < sz(t); i++) t[i]=0;
int j=0;
for (int i = 0; i < sz(v); i++)
{
int l=v[i].first.second.first;
int r=v[i].first.second.second;
int mid=(l+r)/2;
while(j<sz(sh)&&sh[j].first>=v[i].first.first){
update(sh[j].second,1);
j++;
}
int qr=query(que[v[i].second].first,que[v[i].second].second);
if(qr<mid){
r=mid-1;
}else{
ans[v[i].second]=mid;
l=mid+1;
}
if(l<=r){
v2.push_back({{(l+r)/2,{l,r}},v[i].second});
}
}
swap(v,v2);
}
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
return 0;
}
