#include <bits/stdc++.h>
using namespace std;
struct Arbre {
int rd, l, r;
int lb, rb;
int sz;
Arbre(int _lb, int _rb) {
rd = rand();
lb = _lb;
rb = _rb;
l = r = -1;
sz = rb - lb;
}
};
int root = -1;
vector<Arbre> arbres;
int N, Q;
vector<int> nbs;
vector<int> nextBig;
int sz(int a) {
if(a == -1) return 0;
return arbres[a].sz;
}
void pull(int a) {
arbres[a].sz = (arbres[a].rb - arbres[a].lb) + sz(arbres[a].l) + sz(arbres[a].r);
}
int merge(int a, int b) {
if(a == -1) return b;
if(b == -1) return a;
if(arbres[a].rd < arbres[b].rd) {
arbres[a].r = merge(arbres[a].r, b);
pull(a);
return a;
}
else {
arbres[b].l = merge(a, arbres[b].l);
pull(b);
return b;
}
}
pair<int, int> split(int a, int x) {
if(a == -1) return {-1, -1};
if(nbs[arbres[a].lb] < x) {
pair<int, int> rht = split(arbres[a].r, x);
arbres[a].r = -1;
pull(a);
return {merge(a, rht.first), rht.second};
}
else {
pair<int, int> lft = split(arbres[a].l, x);
arbres[a].l = -1;
pull(a);
return {lft.first, merge(lft.second, a)};
}
}
int insert(int root, int lb, int ub) {
pair<int, int> spl = split(root, nbs[lb]);
int id = arbres.size();
arbres.push_back(Arbre(lb, ub));
return merge(merge(spl.first, id), spl.second);
}
int remove(int root, int x) {
pair<int, int> spl1 = split(root, x);
pair<int, int> spl2 = split(spl1.second, x + 1);
return merge(spl1.first, spl2.second);
}
struct Inter {
int l, r;
int li, ri;
};
Inter inter_pos(int a, int pos) {
if(pos < sz(arbres[a].l)) {
return inter_pos(arbres[a].l, pos);
}
pos -= sz(arbres[a].l);
if(pos < arbres[a].rb - arbres[a].lb) {
return {sz(arbres[a].l), sz(arbres[a].l) + arbres[a].rb - arbres[a].lb, arbres[a].lb, arbres[a].rb};
}
pos -= (arbres[a].rb - arbres[a].lb);
Inter res = inter_pos(arbres[a].r, pos);
res.l += sz(arbres[a].l) + (arbres[a].rb - arbres[a].lb);
res.r += sz(arbres[a].l) + (arbres[a].rb - arbres[a].lb);
return res;
}
void debug(int root) {
if(root == -1) return;
debug(arbres[root].l);
cerr << arbres[root].lb << " " << arbres[root].rb << endl;
debug(arbres[root].r);
}
void init() {
vector<int> ouverts;
nextBig = vector<int>(N);
for(int pos = N - 1;pos >= 0;pos--) {
while(!ouverts.empty()
&& nbs[ouverts.back()] <= nbs[pos])
ouverts.pop_back();
if(ouverts.empty()) nextBig[pos] = N;
else nextBig[pos] = ouverts.back();
ouverts.push_back(pos);
}
int start = 0;
while(start != N) {
root = insert(root, start, nextBig[start]);
start = nextBig[start];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> Q;
for(int i = 0;i < N;i++) {
int x;
cin >> x;
nbs.push_back(x);
}
init();
vector<vector<pair<int, int>>> reqs(1 + N);
for(int i = 0;i < Q;i++) {
int t, j;
cin >> t >> j;
reqs[min(N, t)].push_back({i, j - 1});
}
vector<int> ans(Q);
for(int t = 0;t <= N;t++) {
// Answer requests
//cerr << "cur: " << t << endl;
//debug(root);
for(pair<int, int> req : reqs[t]) {
//cerr << "req: " << req.second << " " << req.first << endl;
Inter inter = inter_pos(root, req.second);
//cerr << "ans : " << nbs[inter.li + req.second - inter.l] << endl;
ans[req.first] = nbs[inter.li + req.second - inter.l];
}
// Split in the middle & reorder
Inter spl = inter_pos(root, N / 2);
if(spl.l == N / 2) continue;
root = remove(root, nbs[spl.li]);
vector<pair<int, int>> inters;
inters.push_back({spl.li, spl.li + (N / 2 - spl.l)});
int start = spl.li + N / 2 - spl.l;
while(start != spl.ri) {
inters.push_back({
start,
min(nextBig[start], spl.ri)
});
start = min(nextBig[start], spl.ri);
}
for(pair<int, int> inter : inters) {
root = insert(root, inter.first, inter.second);
}
}
for(int i = 0;i < Q;i++) {
cout << ans[i] << endl;
}
return 0;
}
