#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 2e5 + 10;
int a[N], nxt[N];
struct Node {
Node *l = 0, *r = 0;
int idx, len, c; int y;
Node(int idx, int len) : idx{idx}, len{len}, c{len}, y(rng()) {}
void pull();
};
int cnt(Node* n) { return n ? n->c : 0; }
void Node::pull() { c = cnt(l) + cnt(r) + len; }
template<class F> void each(Node* n, F f) {
if (n) { each(n->l, f); f(n); each(n->r, f); }
}
pair<Node*, int> find_idx(Node* n, int k) {
if (k < cnt(n->l)) return find_idx(n->l, k);
k -= cnt(n->l);
if (k < n->len) return {n, k};
return find_idx(n->r, k - n->len);
}
array<Node*, 3> split_idx(Node* n, int k) {
if (k < cnt(n->l)) {
auto L = split_idx(n->l, k);
n->l = L[2];
n->pull();
return {L[0], L[1], n};
}
k -= cnt(n->l);
if (k < n->len) {
const auto L = n->l, R = n->r;
n->l = n->r = nullptr;
n->pull();
return {L, n, R};
}
k -= n->len;
auto R = split_idx(n->r, k);
n->r = R[0];
n->pull();
return {n, R[1], R[2]};
}
array<Node*, 2> split_val(Node *n, int k) {
if (!n) return {};
if (a[n->idx] >= k) {
auto pa = split_val(n->l, k);
n->l = pa[1];
n->pull();
return {pa[0], n};
} else {
auto pa = split_val(n->r, k);
n->r = pa[0];
n->pull();
return {n, pa[1]};
}
}
/*
pair<Node*, Node*> split(Node* n, int k) {
if (!n) return {};
if (cnt(n->l) >= k) { // "n->val >= k" for lower_bound(k)
auto pa = split(n->l, k);
n->l = pa.second;
n->pull();
return {pa.first, n};
} else {
auto pa = split(n->r, k - cnt(n->l) - 1); // and just "k"
n->r = pa.first;
n->pull();
return {n, pa.second};
}
}
*/
Node* merge(Node* l, Node* r) {
if (!l) return r;
if (!r) return l;
if (l->y > r->y) {
l->r = merge(l->r, r);
l->pull();
return l;
} else {
r->l = merge(l, r->l);
r->pull();
return r;
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
rep(i, 0, n) cin >> a[i];
per(i, 0, n) {
nxt[i] = i + 1;
while (nxt[i] < n and a[nxt[i]] < a[i])
nxt[i] = nxt[nxt[i]];
}
Node* root = nullptr;
for (int i = 0; i < n; i = nxt[i]) {
auto node = new Node(i, nxt[i] - i);
root = merge(root, node);
}
int steps = 0;
auto do_op = [&]() -> bool {
++steps;
const auto [__, s] = find_idx(root, n / 2);
if (s == 0) return true; // no change happens
auto [L, X, R] = split_idx(root, n / 2);
assert(X == __);
const int r = X->idx + X->len;
Node* LL = nullptr;
for (int i = X->idx + s; i < r; i = nxt[i]) {
const auto len = min(nxt[i], r) - i;
Node *node = new Node(i, len);
auto tmp = split_val(L, a[i]);
LL = merge(LL, merge(tmp[0], node));
L = tmp[1];
}
X->len = s;
X->pull();
root = merge(LL, merge(L, merge(X, R)));
return false;
};
/*
auto f = [&](Node* n) {
rep(i, n->idx, n->idx + n->len)
cerr << a[i] << ' ';
};
*/
vector<tuple<int, int, int>> query(q);
{
int ctr = 0;
for (auto &[t, i, idx] : query)
cin >> t >> i, --i, idx = ctr++;
}
sort(all(query));
vector<int> ans(q, -1);
bool stable = false;
for (auto [t, i, idx] : query) {
while (not stable and steps < t)
stable = do_op();
const auto [node, s] = find_idx(root, i);
ans[idx] = a[node->idx + s];
}
for (auto x : ans)
cout << x << '\n';
}
