#include <bits/stdc++.h>
using namespace std;
inline void chmin(int &a, int b) {a = min(a, b);}
inline void chmax(int &a, int b) {a = max(a, b);}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
deque<int> l, r;
for(int i = 0; i < N; i++) {
int x;
cin >> x;
if (i < N/2) {
l.push_back(x);
}
else {
r.push_back(x);
}
}
deque<int> nl, nr;
vector<vector<pair<int,int>>> q(N+1);
vector<int> re(Q);
for(int i = 0; i < Q; i++) {
int t, x;
cin >> t >> x;
x--;
q[min(t, N)].push_back({x,i});
}
int cnt = 0;
for(auto &[i, qi]: q[cnt]) {
if (i >= N/2) re[qi] = r[i-N/2];
else re[qi] = l[i];
}
while(cnt < N) {
cnt++;
while(l.size() && r.size()) {
if (nl.size() >= N/2) {
if (l.front() < r.front()) {nr.push_back(l.front()); l.pop_front();}
else {nr.push_back(r.front()); r.pop_front();}
} else {
if (l.front() < r.front()) {nl.push_back(l.front()); l.pop_front();}
else {nl.push_back(r.front()); r.pop_front();}
}
}
while(l.size()) {nr.push_back(l.front()); l.pop_front();}
while(r.size()) {nr.push_back(r.front()); r.pop_front();}
for(auto &[i, qi]: q[cnt]) {
if (i >= N/2) re[qi] = nr[i-N/2];
else re[qi] = nl[i];
}
l.clear(), r.clear();
swap(l, nl), swap(r, nr);
}
for(int &x: re) cout <<x << endl;
}
