#include <bits/stdc++.h>
using namespace std;
#define int long long
struct fenwick{
vector<int> tree;
fenwick(int N):tree(N+1){}
void add(int k,int x){
while(k<tree.size()){
tree[k]+=x;
k+=k&-k;
}
}
int get(int k){
int ans = 0;
while(k){
ans+=tree[k];
k-=k&-k;
}
return ans;
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,Q;
cin >> N >> Q;
vector<int> arr(N+1);
vector<int> optR(N+1);
vector<int> idx(N+1);
for(int i=1;i<=N;i++){
cin>>arr[i];
idx[arr[i]]=i;
}
{
stack<pair<int,int>> s;
s.emplace(N+1,N+1);
for(int i=N;i;i--){
while(s.top().first<arr[i])s.pop();
optR[i]=s.top().second;
s.emplace(arr[i],i);
}
}
vector<vector<pair<int,int>>> queries(N+1);
vector<int> ans(Q+1);
for(int i=1;i<=Q;i++){
int t,x;cin>>t>>x;
queries[min(t,N)].emplace_back(x,i);
}
for(auto&[pos,id]:queries[0])ans[id]=arr[pos];
fenwick bit(N);
auto solve = [&](int L,int R){
while(L<=R){
int upd = min(optR[L],R+1);
bit.add(arr[L],upd-L);
L = upd;
}
};
solve(1,N/2);
solve(N/2 + 1,N);
for(int round = 1;round<=N;round++){
for(auto&[pos,id]:queries[round]){
int higher = 0;
for(int jump=(1<<17);jump;jump/=2){
if(higher+jump>N)continue;
if(bit.get(higher+jump)<pos)higher+=jump;
}
int prev = bit.get(higher);
ans[id]=arr[pos-prev-1+idx[higher+1]];
}
int ele = 0;
for(int jump=(1<<17);jump;jump/=2){
if(ele+jump>N)continue;
if(bit.get(ele+jump)<N/2)ele+=jump;
}
int prev = bit.get(ele);
ele++;
int L = N/2-prev+idx[ele];
int R = bit.get(ele)-prev-1+idx[ele];
solve(L,R);
bit.add(ele,-(R-L+1));
}
for(int i=1;i<=Q;i++)cout<<ans[i]<<'\n';
}
