#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int fw[N];
void upd(int idx){
for(; idx < N; idx += idx&(-idx)) fw[idx]++;
}
int q(int idx){
int res = 0;
for(; idx > 0; idx -= idx&(-idx)) res += fw[idx];
return res;
}
int query(int l, int r){
return q(r) - q(l-1);
}
int a[N]; //n
int x[N], y[N], l[N], r[N]; //q
vector<int> pos[N]; //max(a[i])
vector<int> queries[N]; //n
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
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] = y[i]-x[i]+2;
}
for(int cnt = 0; cnt < log2(N); ++cnt){
bool finished = 1;
for(int i = 1; i < N; ++i) queries[i].clear();
for(int i = 1; i <= q; ++i){
if(l[i] != r[i]){
finished = 0;
queries[(l[i]+r[i])>>1].push_back(i);
}
}
if(finished) break;
memset(fw, 0, sizeof fw);
for(int i = N-1; i >= 1; --i){
for(int idx : pos[i]) upd(idx);
for(int idx : queries[i]){
if(query(x[idx], y[idx]) >= i) l[idx] = i;
else r[idx] = i;
}
}
}
for(int i = 1; i <= q; ++i){
cout << l[i] << '\n';
}
}
/*
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
*/
