#include<bits/stdc++.h>
#define N 200010
// #define Q 1000010
using namespace std;
int n, q;
vector <pair <int, int>> query;
vector <int> v;
bool ver = false;
void shuff(){
vector <int> aux;
int l = 0, r = n/2;
while(l < n/2 or r < n){
if(l >= n/2){
aux.push_back(v[r]);
r++;
continue;
}
if(r >= n){
aux.push_back(v[l]);
l++;
continue;
}
if(v[l] < v[r]){
aux.push_back(v[l]);
l++;
}
else{
aux.push_back(v[r]);
r++;
}
}
ver = true;
for(int i = 0;i < n;i++){
if(v[i] != aux[i]) ver = false;
}
v = aux;
return;
}
int main(){
cin >> n >> q;
for(int i = 0;i < n;i++){
int x;
cin >> x;
v.push_back(x);
}
map <pair <int, int>, int> m;
for(int i = 0;i < q;i++){
int a, b;
cin >> a >> b;
query.push_back({a, b});
m[{a, b}] = i;
}
vector <pair <int, int>> ans = query;
sort(query.begin(), query.end());
query.push_back({1, 1});
int con = 0;
for(int i = 0;con < q;i++){
if(ver == true){
while(con < q){
m[query[con]] = v[query[con].second-1];
con++;
}
break;
}
while(query[con].first == i and con < q){
m[query[con]] = v[query[con].second-1];
con++;
}
shuff();
}
for(auto x : ans){
cout << m[x] << "\n";
}
return 0;
}
