#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=200007;
ll n,m,k;
int a[N];
int d[N];
int ind[N];
bool met[N];
set<int>s;
int curlen=0;
pair<int,int> t[4*N];
int tt[4*N];
vector<pair<pair<int,int>,int>>q;
int qi=0;
void build(int v, int tl, int tr){
if(tl==tr){
t[v]={a[tl],tl};
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
}
void build2(int v, int tl, int tr){
if(tl==tr){
tt[v]=d[tl];
}
else{
int tm=(tl+tr)/2;
build2(2*v,tl,tm);
build2(2*v+1,tm+1,tr);
tt[v]=tt[2*v]+tt[2*v+1];
}
}
void update(int v, int tl, int tr, int ind, int val){
if(tl==tr){
tt[v]=val;
}
else{
int tm=(tl+tr)/2;
if(ind<=tm){
update(2*v,tl,tm,ind,val);
}
else{
update(2*v+1,tm+1,tr,ind,val);
}
tt[v]=tt[2*v]+tt[2*v+1];
}
}
int getsum(int v, int tl, int tr, int l, int r){
if(l>r)return 0;
if(tl==l&&tr==r){
return tt[v];
}
else{
int tm=(tl+tr)/2;
return getsum(2*v,tl,tm,l,min(r,tm))+
getsum(2*v+1,tm+1,tr,max(tm+1,l),r);
}
}
int binsearch(int indd){
int l=1,r=n+1;
while(l<r){
int mid=(l+r)/2;
if(getsum(1,1,n,mid,n)>indd){
l=mid+1;
}
else{
r=mid;
}
}
return l-1;
}
pair<int,int> getmax(int v, int tl, int tr, int l, int r){
if(l>r)return {0,0};
if(tl==l&&tr==r){
return t[v];
}
else{
int tm=(tl+tr)/2;
return max(getmax(2*v,tl,tm,l,min(r,tm)),
getmax(2*v+1,tm+1,tr,max(tm+1,l),r));
}
}
int stepcnt=0;
void step(vector<int>&ans){
while(qi!=m&&q[qi].ff.ff==stepcnt){
int indd=n-q[qi].ff.ss-1;
int cmp=binsearch(indd);
int cmpind=getsum(1,1,n,cmp,n)-1;
ans[q[qi].ss]=a[ind[cmp]-(cmpind-indd)];
qi++;
}
stepcnt++;
// cout<<"step"<<endl;
while(curlen+d[-(*s.begin())]<=n/2){
curlen+=d[-(*s.begin())];
s.erase(s.begin());
}
int v=-(*s.begin());
int i=ind[v];
int len=d[v];
// cout<<v<<" "<<i<<" "<<len<<endl;
int l=ind[v]-d[v]+1;
int r=n/2-curlen+l-1;
d[v]=i-r;
update(1,1,n,v,d[v]);
// cout<<l<<" "<<r<<endl;
while(l<=r){
pair<int,int>e=getmax(1,0,n-1,l,r);
int mx=e.ff;
int mxi=e.ss;
int newlen=mxi-l+1;
d[mx]=newlen;
update(1,1,n,mx,d[mx]);
ind[mx]=mxi;
s.insert(-mx);
l=mxi+1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("Ainput.txt","r",stdin);
// freopen("Aoutput.txt","w",stdout);
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[n-i-1];
}
build(1,0,n-1);
int lsti=-1;
int mx=n;
int i=0;
while(i!=n){
while(i!=n&&a[i]<mx){
met[a[i]]=true;
i++;
}
d[mx]=i-lsti;
ind[mx]=i;
s.insert(-mx);
met[mx]=true;
while(met[mx]){
mx--;
}
lsti=i;
i++;
}
build2(1,1,n);
int t=0;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
y--;
q.push_back({{x,y},i});
// t=x;
}
sort(q.begin(),q.end());
vector<int>ans(m,0);
for(int i=0;i<n*5;i++){
step(ans);
}
while(qi!=m){
int indd=n-q[qi].ff.ss-1;
int cmp=binsearch(indd);
int cmpind=getsum(1,1,n,cmp,n)-1;
ans[q[qi].ss]=a[ind[cmp]-(cmpind-indd)];
qi++;
}
for(int i=0;i<m;i++){
cout<<ans[i]<<endl;
}
}
