#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
struct query{
int t,i,ind;
};
struct Node{
int val,maxi,sz,pri;
Node*l,*r;
Node(int val):val(val),maxi(val),sz(1),pri(rand()),l(0),r(0){}
};
using pnode=Node*;
int getcnt(pnode p){
if(p)return p->sz;
return 0;
}
int getval(pnode p){
if(p)return p->maxi;
return 0;
}
void upd(pnode p){
if(p){
p->sz=getcnt(p->l)+getcnt(p->r)+1;
p->maxi=p->val;
if(p->l)p->maxi=max(p->maxi,p->l->maxi);
if(p->r)p->maxi=max(p->maxi,p->r->maxi);
}
}
void merge(pnode&p,pnode l,pnode r){
if(!l){
p=r;
return;
}
if(!r){
p=l;
return;
}
if(l->pri<r->pri){
merge(r->l,l,r->l);
p=r;
}else{
merge(l->r,l->r,r);
p=l;
}
upd(p);
}
void splitind(pnode p,pnode&l,pnode&r,int ind){
if(!p){
l=r=0;
return;
}
if(getcnt(p->l)+1<ind){
splitind(p->r,p->r,r,ind-getcnt(p->l)-1);
l=p;
}else{
splitind(p->l,l,p->l,ind);
r=p;
}
upd(p);
}
void split(pnode p,pnode&l,pnode&r,int val){
if(!p){
l=r=0;
return;
}
if(max(p->val,getval(p->l))<=val){
split(p->r,p->r,r,val);
l=p;
}else{
split(p->l,l,p->l,val);
r=p;
}
upd(p);
}
int find(pnode p,int ind){
if(ind==getcnt(p->l)+1)return p->val;
if(ind<getcnt(p->l)+1)return find(p->l,ind);
return find(p->r,ind-getcnt(p->l)-1);
}
int beg(pnode p){
if(p->l)return beg(p->l);
return p->val;
}
pnode last(pnode p){
if(p->r)return last(p->r);
return p;
}
void walk(pnode p){
if(!p)return;
walk(p->l);
//cerr<<p->val<<' ';
walk(p->r);
}
int main(){
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int n,m;
cin>>n>>m;
int a[n];
pnode t1=0,t2=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(i<n/2)merge(t1,t1,new Node(a[i]));
else merge(t2,t2,new Node(a[i]));
}
query q[m];
for(int i=0;i<m;i++){
cin>>q[i].t>>q[i].i;
q[i].ind=i;
}
sort(q,q+m,[&](query x,query y)->bool {
return x.t<y.t;
});
bool done=0;
int turn=0;
int ans[m];
for(int i=0;i<m;i++){
while(turn<q[i].t&&!done){
done=1;
turn++;
bool cont;
//cerr<<"begin\n";
do{
cont=0;
//cerr<<"begin again\n";
int val=beg(t2);
//cerr<<"found\n";
pnode p1=0,p2=0;
split(t1,p1,p2,val);
if(p2!=0){
cont=1;
done=0;
pnode p3=0;
//cerr<<"sp beg\n";
split(t2,p3,t2,val);
merge(t1,p1,p3);
merge(t1,t1,p2);
//cerr<<"sp end\n";
}
//cerr<<"here\n";
}while(cont&&getcnt(t2));
//cerr<<"end\n";
while(n/2<getcnt(t1)){
pnode p=0;
splitind(t1,t1,p,n/2+1);
merge(t2,p,t2);
}
//cerr<<"check\n";
}
//walk(t1);cerr<<'\n';walk(t2);
//cerr<<'\n';
if(q[i].i<=n/2){
ans[q[i].ind]=find(t1,q[i].i);
}else{
//cerr<<q[i].i-n/2<<" huh\n";
ans[q[i].ind]=find(t2,q[i].i-n/2);
}
//cerr<<"ok\n";
//cerr<<ans[q[i].ind]<<'\n';
}
for(int i:ans)cout<<i<<'\n';
}
