#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;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
map<int, vector<int>> mp_l, mp_r;
vector<int> st(q + 1, 0), en(q + 1, 0), p(q + 1, 0);
for(int i = 1, l, r; i <= q; ++i){
cin >> l >> r;
mp_l[l].push_back(i);
mp_r[r].push_back(i);
st[i] = 1, en[i] = n + 1;
p[i] = (st[i] + en[i]) / 2;
}
vector<int> ans(q + 1, 0);
for(int _ = 0; _ < 20; ++_){
vector<int> cseen(q + 1, 0);
pbds oset;
for(int i = 1; i <= n; ++i){
for(auto it : mp_l[i]){
cseen[it] = -oset.order_of_key(p[it] - 1);
}
oset.insert(a[i]);
for(auto it : mp_r[i]){
cseen[it] += oset.order_of_key(p[it] - 1);
if(st[it] > en[it]) continue;
if(cseen[it] >= p[it]){
st[it] = p[it] + 1;
ans[it] = p[it];
}else{
en[it] = p[it] - 1;
}
}
}
for(int i = 1; i <= q; ++i){
if(st[i] <= en[i]){
p[i] = (st[i] + en[i]) / 2;
}
}
}
for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
return 0;
}
