#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];
vector <int> pos[1000005];
pair<int,int> q[1000005];
vector <int> v[1000005];
int res[1000005];
int l[1000005];
int r[1000005];
int bit[1000005];
vector <int> used;
void update(int i,int val){
i++;
while (i<=a+64){
if (bit[i]==0){
used.push_back(i);
}
bit[i]+=val;
i+=i&-i;
}
}
int query(int i){
i++;
int res=0;
while (i>0){
res+=bit[i];
i-=i&-i;
}
return res;
}
void reset(){
for (auto p:used){
bit[p]=0;
}
used.clear();
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
int max1=0;
for (int i=1;i<=a;i++){
cin >> z[i];
pos[z[i]].push_back(i);
max1=max(max1,z[i]);
}
for (int i=1;i<=b;i++){
cin >> q[i].first >> q[i].second;
l[i]=1;
r[i]=max1;
}
// cout << "\n";
while (true){
bool check=true;
for (int i=1;i<=b;i++){
if (l[i]<=r[i]){
check=false;
int mid=(l[i]+r[i])/2;
v[mid].push_back(i);
}
}
if (check){
break;
}
reset();
for (int i=max1;i>=1;i--){
for (auto p:pos[i]){
update(p,1);
}
for (auto p:v[i]){
int sl=query(q[p].second)-query(q[p].first-1);
// cout << sl << " " << q[p].first << " " << q[p].second << "\n";
if (sl>=i){
res[p]=i;
l[p]=i+1;
}else{
r[p]=i-1;
}
}
v[i].clear();
}
}
for (int i=1;i<=b;i++){
cout << res[i] << "\n";
}
return 0;
}
