#include<bits/stdc++.h>
#define endl '\n'
#define de(x) cout << #x << " = " << x << endl;
#define all(A) A.begin(), A.end()
using namespace std;
const int MAXN = 2e5;
const int MAXQ = 1e6;
ostream& operator<<(ostream& out, array<int, 3> v){
out << "(" << v[0] << " " << v[1] << " " << v[2] << ")";
return out;
}
struct Treap{
struct Node{
array<int, 3> val;
int my_size, acc_size;
int prior;
Node *lc, *rc;
Node() {}
Node(array<int, 3> val) : val(val), prior(rand()), lc(nullptr), rc(nullptr), my_size(val[2] - val[1] + 1), acc_size(val[2] - val[1] + 1) {}
void update(){
acc_size = my_size + (lc == nullptr ? 0 : lc -> acc_size) + (rc == nullptr ? 0 : rc -> acc_size);
}
};
Node* root;
pair<Node*, Node*> split(Node* node, array<int, 3> key){
if(node == nullptr) return {nullptr, nullptr};
if(node -> val <= key){
auto [lt, rt] = split(node -> rc, key);
node -> rc = lt;
node -> update();
return {node, rt};
}
else{
auto [lt, rt] = split(node -> lc, key);
node -> lc = rt;
node -> update();
return {lt, node};
}
}
Node* merge(Node* lt, Node* rt){
if(lt == nullptr) return rt;
if(rt == nullptr) return lt;
if(lt -> prior < rt -> prior){
rt -> lc = merge(lt, rt -> lc);
rt -> update();
return rt;
}
else{
lt -> rc = merge(lt -> rc, rt);
lt -> update();
return lt;
}
}
void insert(array<int, 3> key){
auto [lt, rt] = split(root, key);
auto mt = new Node(key);
root = merge(merge(lt, mt), rt);
}
void erase(array<int, 3> low_key, array<int, 3> high_key){
auto [lt, mrt] = split(root, low_key);
auto [mt, rt] = split(mrt, high_key);
root = merge(lt, rt);
}
void util_print(Node* node){
if(node == nullptr) return;
util_print(node -> lc);
cout << node -> val << " ";
util_print(node -> rc);
}
void print(){ util_print(root); cout << endl; }
array<int, 3> util_search(Node* node, int &to_left, int key){
if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key && to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) + (node -> my_size) >= key){
to_left += (node -> lc == nullptr ? 0 : node -> lc -> acc_size);
return node -> val;
}
else if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key){
to_left += (node -> acc_size) - (node -> rc -> acc_size);
return util_search(node -> rc, to_left, key);
}
else{
return util_search(node -> lc, to_left, key);
}
}
pair<int, array<int, 3>> search(int key){
int shift = 0;
auto ret = util_search(root, shift, key);
return {shift, ret};
}
};
int n, q, a[MAXN + 5], ans[MAXQ + 5], nxt[MAXN + 5];
vector<array<int, 3>> queries;
Treap tr;
bool riffle_shuffle(){
vector<int> v;
vector<int> lft, rgt;
for(int i = 1; i <= n; i ++){
(i <= n / 2 ? lft : rgt).push_back(a[i]);
}
for(int i = 0, j = 0; v.size() < n; ){
if(i == n / 2) v.push_back(rgt[j ++]);
else if(j == n / 2) v.push_back(lft[i ++]);
else if(lft[i] < rgt[j]){
v.push_back(lft[i ++]);
}
else{
v.push_back(rgt[j ++]);
}
}
bool flag = false;
for(int i = 1; i <= n; i ++){
if(a[i] != v[i - 1]) flag = true;
a[i] = v[i - 1];
}
return flag;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
for(int i = 0; i < q; i ++){
int x, t; cin >> t >> x;
queries.push_back({t, x, i});
}
sort(all(queries));
int cur_time = 0;
for(auto [t, x, idx] : queries){
while(cur_time < t){
if(riffle_shuffle()) ++ cur_time;
else cur_time = t;
}
ans[idx] = a[x];
}
for(int i = 0; i < q; i ++){
cout << ans[i] << endl;
}
}
/*
*/
