#include <bits/stdc++.h>
using namespace std;
int n,q;
int a[200001];
int p[1001][1001];
int t,x;
void read()
{
cin>>n>>q;
for(int i=1; i<=n; i++)
{
cin>>a[i];
p[0][i]=a[i];
}
}
int nxt[200001];
void prec1()
{
for(int i=1; i<=n; i++)
{
int j=1;
int i1=1,i2=n/2+1;
while(i1<=n/2||i2<=n)
{
if(i1>n/2)p[i][j++]=p[i-1][i2++];
else if(i2>n)p[i][j++]=p[i-1][i1++];
else if(p[i-1][i1]<p[i-1][i2])p[i][j++]=p[i-1][i1++];
else p[i][j++]=p[i-1][i2++];
}
}
}
void solve1()
{
for(int i=1; i<=q; i++)
{
int t,id;
cin>>t>>id;
cout<<p[min(n,t)][id]<<endl;
}
}
struct group
{
int id;
group() {}
group(int _id)
{
id=_id;
}
bool operator<(const group&g)const
{
return a[id]<a[g.id];
}
};
set<group> s;
int b[200001];
int sz[200001];
void solve()
{
for(int i=1;i<=n;i++)
b[i]=a[i];
stack<int> h;
for(int i=n;i>=1;i--)
{
while(h.size()&&a[h.top()]<a[i])h.pop();
if(h.size())nxt[i]=h.top();
else nxt[i]=n+1;
h.push(i);
}
cin>>t>>x;
int i=1;
while(i<=n)
{
int j=i;
while(j<=n&&a[j]<=a[i])j++;
s.insert({i});
//cout<<i<<" - "<<j-i<<endl;
sz[i]=j-i;
i=j;
}
//cout<<"here"<<endl;
auto it=s.begin();
int cnt=0;
int br=-1;
while(cnt<n/2)
{
cnt+=sz[it->id];
//cout<<"! "<<cnt<<endl;
if(cnt>n/2)
br=it->id;
else it++;
}
cnt-=sz[it->id];
/*cout<<br<<" > "<<cnt<<endl;
for(int i=1;i<=n;i++)
cout<<i<<" --- "<<sz[i]<<endl;*/
/*if(br!=-1)
{
int lp=0;
while(lp<t)
{
lp++;
it=s.find({br});
int nid=it->id+n/2-cnt;
int rt=it->id+sz[it->id];
int cnt1=cnt+sz[br];
s.erase(it);
sz[br]=n/2-cnt;
s.insert({br});
while(nid<rt)
{
sz[nid]=nxt[nid]-nid;
s.insert({nid});
nid=nxt[nid];
}
//cout<<"!!!! "<<nid<<" "<<sz[nid]<<" "<<br<<" "<<sz[br]<<endl;
cnt=cnt1;
bool f=0;
it=s.find({br});
while(cnt>n/2)
{
cnt-=sz[it->id];
if(cnt==n/2)f=1;
else if(cnt<n/2)br=it->id;
else it--;
}
/*cout<<"! "<<br<<" "<<cnt<<endl;
for(auto it1=s.begin();it1!=s.end();it1++)
cout<<it1->id<<" "<<sz[it1->id]<<endl;
cout<<"over"<<endl;
cout<<endl;
if(f)break;
}
//for(int i=1;i<=n;i++)
// cout<<i<<" 0 "<<sz[i]<<endl;
i=1;
for(it=s.begin(); it!=s.end(); it++)
{
group g=*it;
int j=sz[g.id];
//cout<<g.id<<" 0> "<<sz[g.id]<<endl;
while(j--)
{
b[i++]=a[g.id];
g.id++;
}
}
}*/
cout<<b[x]<<endl;
for(int i=1; i<q; i++)
{
cin>>t>>x;
cout<<b[x]<<endl;
}
/*for(int i=1;i<=n;i++)
cout<<b[i]<<" ";
cout<<endl;*/
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
if(n<=1)
{
prec1();
solve1();
}
else
{
solve();
}
return 0;
}
/*
10 0
3 2 7 5 4 6 1 8 9 10
*/
/*
8 8
5 2 7 3 1 6 8 4
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
8 8
5 2 7 3 1 6 8 4
3 1
1
3 2
6
3 3
5
3 4
2
3 5
7
3 6
3
3 7
8
3 8
4
*/
