#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,q;
vector<int> ans;
vector<vector<array<int,2>>> calc;
void f(vector<int> v,int kac){
if(kac>=2*n+2) return;
for(auto x:calc[kac]) ans[x[1]]=v[x[0]-1];
vector<int> res;
int p1 = 0, p2 = n / 2;
while(p1<n/2 && p2<n){
if(v[p1]<v[p2]) res.push_back(v[p1++]);
else res.push_back(v[p2++]);
}
while(p1<n/2) res.push_back(v[p1++]);
while(p2<n) res.push_back(v[p2++]);
f(res,kac+1);
return;
}
void _(){
cin >> n >> q;
calc.resize(2*n+5);
ans.resize(q+5);
vector<int> ar;
for(int i=0;i<n;i++){
int a;cin >> a;
ar.push_back(a);
}
for(int i=1;i<=q;i++){
int a,b;
cin >> a >> b;
calc[min(2*n+1,a)].push_back({b,i});
}
f(ar,0);
for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
