#include<bits/stdc++.h>
using namespace std;
int ar[200005];
vector<pair<int,int>>qr[200005];
int ans[1000005];
int vis[200005];
mt19937 rng(67);
struct node{
int val,prio,mx,sz;
node *l,*r;
node(int _val=0){
mx=val=_val;
l=r=NULL;
sz=1;
prio=rng();
}
};
typedef node* pnode;
int gval(pnode &a){
return a?a->val:0;
}
int gmx(pnode &a){
return a?a->mx:0;
}
int gsz(pnode &a){
return a?a->sz:0;
}
void pull(pnode &a){
if(!a)return;
a->mx=max({a->val,gmx(a->l),gmx(a->r)});
a->sz=gsz(a->l)+gsz(a->r)+1;
}
void merge(pnode a,pnode b,pnode &c){
if(!a)return c=b,void();
if(!b)return c=a,void();
if(a->prio>b->prio)merge(a->r,b,a->r),c=a;
else merge(a,b->l,b->l),c=b;
pull(c);
}
void split(pnode a,pnode &b,pnode &c,int val){
if(!a)return void(b=c=NULL);
//cerr<<"s:"<<a->val<<" "<<gval(a->l)<<" "<<gval(a->r)<<"\n";
if(gmx(a->l)>val)split(a->l,b,a->l,val),c=a;
else if(a->val>val){
b=a->l;
a->l=NULL;
c=a;
}
else split(a->r,a->r,c,val),b=a;
pull(b),pull(c);
}
void split2(pnode a,pnode &b,pnode &c,int val){
if(!a)return void(b=c=NULL);
if(gsz(a->l)>=val)split2(a->l,b,a->l,val),c=a;
else split2(a->r,a->r,c,val-gsz(a->l)-1),b=a;
pull(b),pull(c);
}
void print(pnode a){
if(!a)return;
print(a->l);
cerr<<a->val<<' ';
print(a->r);
}
pnode rt=NULL;
int gans(int val){
//cerr<<"gans "<<val<<"\n";
pnode a=NULL,b=NULL,c=NULL;
pnode temp=NULL;
split2(rt,a,temp,val-1);
//cerr<<gsz(a)<<" "<<gsz(b)<<" "<<gsz(c)<<"\n";
split2(temp,b,c,1);
//cerr<<"split\n";
//cerr<<gsz(a)<<" "<<gsz(b)<<" "<<gsz(c)<<"\n";
int ans=b->val;
merge(a,b,rt);
merge(rt,c,rt);
//cerr<<"msz:"<<rt->sz<<"\n";
return ans;
}
int main(){
int a=rng();
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,q;cin>>n>>q;
vector<int>v;
for(int i=1;i<=n;i++){
cin>>ar[i],v.push_back(ar[i]);
pnode temp=new node(ar[i]);
merge(rt,temp,rt);
}
//cerr<<rt->sz<<"\n";
//cerr<<"work\n";
for(int i=0;i<q;i++){
int a,b;cin>>a>>b;
a=min(a,n);
qr[a].push_back({b,i});
}
for(auto [a,id]:qr[0]){
//ans[id]=v[a-1];
ans[id]=gans(a);
}
//for(auto x:v)cerr<<x<<" ";
//cerr<<"\n";
//print(rt);
//cerr<<"\n";
for(int i=1;i<=n;i++){
pnode l=NULL,r=NULL;
pnode temp=NULL,temp2=NULL;
split2(rt,l,r,n/2);
pnode ll=NULL;
/*cerr<<"splith\n";
print(l);
cerr<<"\n";
print(r);
cerr<<"\n";*/
while(r){
pnode cur=NULL,res=NULL;
split2(r,temp,temp2,1);
/*cerr<<"gf:\n";
print(temp);
cerr<<"\n";
print(temp2);
cerr<<"\n";*/
int val=temp->val;
merge(temp,temp2,r);
if(vis[val])break;
vis[val]=1;
//print(r);
//cerr<<"\n";
//cerr<<"val:"<<val<<"\n";
split(r,cur,r,val);
/*cerr<<"split r\n";
print(cur);
cerr<<"\n";
print(r);
cerr<<"\n";*/
split(l,temp,temp2,val);
merge(temp,cur,temp);
merge(ll,temp,ll);
l=temp2;
//cerr<<"splitc\n";
//print(ll);
//cerr<<"\n";
//print(l);
//cerr<<"\n";
//print(r);
//cerr<<"\n";
}
merge(ll,l,rt);
merge(rt,r,rt);
for(auto [a,id]:qr[i]){
ans[id]=gans(a);
}
//print(rt);
//cerr<<"\n";
//for(auto x:v)cerr<<x<<" ";
//cerr<<"\n";
}
for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
