#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class x>
// using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class x>
// using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define mod 1'000'000'007
const int mxn = 200001;
const int N = 1 << (__lg(mxn) + 1);
int T[2 * N];
void U(int v, int x){
T[v] = x;
v /= 2;
while(v > 0){
T[v] = T[2 * v] + T[2 * v + 1];
v /= 2;
}
}
int Q(int ql, int qr, int node = 1, int lq = 1, int rq = N){
if(lq > qr || rq < ql){
return 0;
}
if(lq >= ql && rq <= qr){
return T[node];
}
int mid = (lq + rq) / 2;
return Q(ql, qr, 2 * node, lq, mid) + Q(ql, qr, 2 * node + 1, mid + 1, rq);
}
int n, q;
int a[mxn];
int x[mxn], y[mxn], l[mxn], r[mxn], m[mxn], ans[mxn];
vector<int> queries[mxn];
vector<int> pos[mxn];
void pbs(){
bool valid = 1;
while(valid){
memset(T, 0, sizeof T);
for(int i = 1; i <= q; i++){
if(l[i] <= r[i]){
m[i] = (l[i] + r[i]) / 2;
queries[m[i]].push_back(i);
}
}
for(int i = mxn - 1; i > 0; i--){
for(auto j : pos[i]){
U(j + N - 1, 1);
}
for(int j : queries[i]){
int num = Q(x[j], y[j]);
if(num >= i){
ans[j] = max(i, ans[j]);
l[j] = m[j] + 1;
}
else{
r[j] = m[j] - 1;
}
}
}
valid = 0;
for(int i = 1; i <= q; i++){
if(l[i] <= r[i]){
valid = 1;
}
}
for(int i = 1; i <= q; i++){
queries[i].clear();
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>q;
for(int i = 1; i <= n; i++){
cin>>a[i];
pos[a[i]].push_back(i);
}
for(int i = 1; i <= q; i++){
cin>>x[i]>>y[i];
l[i] = 1, r[i] = n;
}
pbs();
for(int i = 1; i <= q; i++){
cout<<ans[i]<<'\n';
}
return 0;
}
