#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
struct FenwickTree{
int n; vector<int> t;
void init(int _n){
n=_n;
t.assign(n+1, 0);
}
void update(int pos, int val){
for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
}
void init(int _n, int* a){
init(_n);
for (int i=1; i<=n; ++i) update(i, a[i]);
}
int get(int pos){
int ans=0;
for (int i=pos; i; i-=i&(-i)) ans+=t[i];
return ans;
}
int get(int l, int r){
return get(r)-get(l-1);
}
} bit;
const int N=2e5+1;
int n, q;
int l[N], r[N], a[N];
pair<int, int> qq[N];
vector<int> v[N], pos[N];
void solve(int tc){
// cout << "Case #" << tc << ": ";
cin >> n >> q;
vector<int> vals;
for (int i=1; i<=n; ++i) cin >> a[i], pos[a[i]].push_back(i);
for (int i=1; i<=q; ++i){
cin >> qq[i].first >> qq[i].second;
l[i]=1, r[i]=2e5;
}
for (int rep=1; rep<=20; ++rep){
for (int i=1; i<=q; ++i) if (l[i]<=r[i]) v[(l[i]+r[i])>>1].push_back(i);
bit.init(n);
for (int i=2e5; i>=1; --i){
for (int j:pos[i]) bit.update(j, 1);
for (int j:v[i]){
if (bit.get(qq[j].first, qq[j].second)>=i) l[j]=i+1;
else r[j]=i-1;
}
v[i].clear();
}
}
for (int i=1; i<=q; ++i) cout << r[i] << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve(i);
return 0;
}
