#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct qry{
ll t,i,qid;
bool operator<(const qry& qr)const{
if(t!=qr.t)return t<qr.t;
if(i!=qr.i)return i<qr.i;
return qid<qr.qid;
}
};
struct SEG{
vector<pair<ll,ll> >seg;
vector<ll>cnt;
ll _n;
void init(ll n){
_n=n;
seg.resize(4*n+5);
cnt.resize(4*n+5,0);
}
void upd(ll ul, ll l, ll r, pair<ll,ll>val, ll id){
if(l==r){
seg[id]=val;
cnt[id]=val.second-val.first+1;
return;
}
ll mid=(l+r)>>1;
if(ul<=mid) upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
cnt[id]=cnt[id*2]+cnt[id*2+1];
}
ll bs(ll l, ll r, ll k, ll id){
if(l==r) return l;
ll mid=(l+r)>>1;
if(cnt[id*2]>=k) return bs(l,mid,k,id*2);
else return bs(mid+1,r,k-cnt[id*2],id*2+1);
}
pair<ll,ll> pairfinding(ll ul, ll l, ll r, ll id){
if(l==r){
return seg[id];
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
return pairfinding(ul,l,mid,id*2);
}
else return pairfinding(ul,mid+1,r,id*2+1);
}
}
ll sum(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return cnt[id];
ll mid=(l+r)>>1;
return sum(ql,qr,l,mid,id*2)+sum(ql,qr,mid+1,r,id*2+1);
}
ll find(){
return bs(1,_n,_n/2+1,1);
}
}st;
ll n;
ll nxt[200005];
ll a[200005];
void start_shuffle(){
ll cur=st.find();
ll tot=st.sum(1,cur,1,n,1);
pair<ll,ll>rng=st.pairfinding(cur,1,n,1);
ll rngsum=rng.second-rng.first+1;
if(tot-rngsum==n/2) return;
tot-=rngsum;
ll diff=n/2-tot;
pair<ll,ll>bruh={rng.first,rng.first+diff-1};
st.upd(cur,1,n,bruh,1);
ll curid=bruh.second+1;
while(1){
if(nxt[curid]>rng.second){
st.upd(a[curid],1,n,{curid,rng.second},1);break;
}
else{
st.upd(a[curid],1,n,{curid,nxt[curid]-1},1);
curid=nxt[curid];
}
}
}
ll find_id(ll idd){
ll cur=st.bs(1,n,idd,1);
pair<ll,ll>rng=st.pairfinding(cur,1,n,1);
ll tot=st.sum(1,cur,1,n,1);
ll rngsum=rng.second-rng.first+1;
tot-=rngsum;
return a[rng.first+idd-tot-1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll q;
cin>>n>>q;
st.init(n);
for(int i=1;i<=n;i++)cin>>a[i];
vector<qry>qrs;
int cnt=1;
while(q--){
ll t,i;
cin>>t>>i;
t=min(t,n);
qrs.push_back({t,i,cnt});
cnt++;
}
sort(qrs.begin(),qrs.end());
ll shuffles=0;
ll ans[qrs.size()+5];
ll newarr[n+5];
newarr[0]=0;
for(int i=1;i<=n;i++){
newarr[i]=max(newarr[i-1],a[i]);
}
ll ptr=1;
for(int i=1;i<=n;i++){
if(newarr[i]!=newarr[i-1]){
st.upd(newarr[i-1],1,n,{ptr,i-1},1);
ptr=i;
}
}
st.upd(newarr[n],1,n,{ptr,n},1);
stack<pair<ll,ll> >s;
for(int i=1;i<=n;i++){
while(s.size()){
if(a[i]>s.top().second){
nxt[s.top().first]=i; s.pop();
}
else break;
}
s.push({i,a[i]});
}
while(s.size()){
nxt[s.top().first]=300000;
s.pop();
}
for(int i=0;i<qrs.size();i++){
while(shuffles<qrs[i].t){
shuffles++;
start_shuffle();
}
ans[qrs[i].qid]=find_id(qrs[i].i);
}
for(int i=1;i<=cnt-1;i++){
cout<<ans[i]<<'\n';
}
}
