#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define fi first
#define se second
#define endl "\n"
//~ #define int long long
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
const int inf = 1e9+7;
const int mod = 2019201997;
//~ const int mod2 = 999983;
typedef long long ll;
int n, q;
vector<int> lleft, rright, val, roots;
int newNode(){
//~ cout<<lleft.size()<< "jakakjkja"<<endl;
lleft.pb(-1);
rright.pb(-1);
val.pb(0);
//~ cout<<lleft.size()<<" jajsjsjsajs"<<endl;
return lleft.size()-1;
}
int newNode(int node){
//~ cout<<lleft.size()<< "aajjakkjakja "<<node<<endl;
lleft.pb(lleft[node]);
rright.pb(rright[node]);
val.pb(val[node]);
return lleft.size()-1;
}
void update(int node, int l, int r, int u, int v){
//~ cerr<<node<<" :: "<<l<<" :: "<<r<<" :: "<<u<<" :: "<<v<<endl;
if(u<l || u>r)return;
if(l==r){
val[node]+=v;
return;
}
int m = (l+r)/2;
if(u<=m){
if(lleft[node] == -1){
//int t=newNode();
lleft[node] = newNode();
//~ cerr<<lleft[node]<<"llefelft"<<endl;
}
lleft[node] = newNode(lleft[node]);
update(lleft[node], l, m, u, v);
}
else{
//~ cout<<rright[node]<<endl;
if(rright[node] == -1){
//int t=newNode();
rright[node] = newNode();
//~ cout<<rright[node]<<"rrigtht"<<endl;
}
//~ cout<<rright[node]<<endl;
rright[node] = newNode(rright[node]);
update(rright[node], m+1, r, u, v);
}
val[node] = lleft[node]!=-1 ? val[lleft[node]] : 0;
val[node] += rright[node]!=-1 ? val[rright[node]] : 0;
}
int query(int node, int l, int r, int s, int f){
if(l>f || r<s)return 0;
if(l>=s && r<=f)return val[node];
int m = (l+r)/2;
int t1 = lleft[node] != -1 ? query(lleft[node], l, m, s, f) : 0;
int t2 = rright[node] != -1 ? query(rright[node], m+1, r, s, f) : 0;
return t1+t2;
}
int32_t main(){
fast;
cin>>n>>q;
int a[n+5];
vector<vector<int>> v;
v.assign(2e5+5, vector<int>());
for(int i=1;i<=n;i++){
cin>>a[i];
v[a[i]].pb(i);
}
roots.pb(newNode());
//~ roots.pb(newNode());
for(int i=1;i<=2e5;i++){
roots.pb(newNode(roots.back()));
for(auto it: v[i]){
update(roots.back(), 1, n, it, 1);
}
//~ cerr<<"pitipiti"<<endl;
}
//~ cerr<<"pitipitti"<<endl;
while(q--){
int a, b;
cin>>a>>b;
int l = 1, r = 2e5;
while(l<=r){
int m = (l+r)/2;
//~ cout<<query(roots.back(), 1, n, a, b)-query(roots[m], 1, n, a, b)<<" :: "<<l<<" :: "<<r<<" :: "<<m<<endl;
if(query(roots.back(), 1, n, a, b)-(m>0 ? query(roots[m-1], 1, n, a, b) : 0)>=m){
l=m+1;
}
else r=m-1;
}
cout<<r<<endl;
//~ cout<<r<<" :: "<<query(roots.back(), 1, n, a, b)-query(roots[r], 1, n, a, b)<<endl;
}
}
