#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;
namespace T1 {
ll base;
vc<ll> t;
void init(ll n) {
base = 1;
while (base < n)
base *= 2;
t.assign(2 * base, 0);
}
void add(ll i, ll x) {
i += base;
while (i >= 1) {
t[i] += x;
i /= 2;
}
}
ll find(ll qx, ll i = 1) {
if (i >= base)
return i - base;
ll li = 2 * i;
if (t[li] >= qx)
return find(qx, li);
return find(qx - t[li], li + 1);
}
ll sum(ll l, ll r) {
ll ret = 0;
l += base - 1;
r += base + 1;
while (l + 1 < r) {
if (l % 2 == 0)
ret += t[l + 1];
if (r % 2 == 1)
ret += t[r - 1];
l /= 2;
r /= 2;
}
return ret;
}
};
namespace T2 {
ll base;
vc<ll> t;
void init(vc<ll> &a) {
base = 1;
while (base < sz(a))
base *= 2;
t.assign(2 * base, -INF);
for (ll i = 0; i < sz(a); i++)
t[i + base] = a[i];
for (ll i = base - 1; i >= 1; i--)
t[i] = max(t[2 * i], t[2 * i + 1]);
}
ll rec(ll qx, ll i) {
if (i >= base)
return i - base;
if (t[2 * i] >= qx)
return rec(qx, 2 * i);
return rec(qx, 2 * i + 1);
}
ll find(ll i) {
i += base;
ll l = i - 1;
ll r = 2 * base;
ll ret = INF;
while (l + 1 < r) {
if (l % 2 == 0 and t[l + 1] > t[i])
ret = rec(t[i] + 1, l + 1);
l /= 2;
r /= 2;
}
return ret;
}
}
struct Que {
ll t, i, id;
};
ll n, q;
vc<ll> a, b;
vc<Que> ques;
void input() {
cin >> n >> q;
a.resize(n);
for (ll &ai : a) {
cin >> ai;
ai--;
}
ques.resize(q);
for (ll i = 0; i < q; i++) {
auto &que = ques[i];
cin >> que.t >> que.i;
que.i--;
que.id = i;
}
}
void init() {
T1::init(n);
T2::init(a);
for (ll i = 0; i < n; ) {
ll j = min(n, T2::find(i));
T1::add(a[i], j - i);
i = j;
}
b.resize(n);
for (ll i = 0; i < n; i++)
b[a[i]] = i;
}
bool apply() {
ll x = T1::find(n / 2);
ll k = T1::sum(0, x);
if (k == n / 2)
return false;
ll l = b[x];
ll r = l + T1::sum(x, x) - 1;
T1::add(x, n / 2 - k);
l += T1::sum(x, x);
while (l <= r) {
ll i = min(r + 1, T2::find(l));
T1::add(a[l], i - l);
l = i;
}
return true;
}
ll get(ll i) {
ll x = T1::find(i + 1);
i -= T1::sum(0, x - 1);
return a[b[x] + i] + 1;
}
void sweep() {
vc<ll> res(q);
sort(all(ques), [](auto &p, auto &q) {
return p.t < q.t;
});
ll cnt = 0;
init();
for (auto &que : ques) {
while (cnt < que.t) {
if (apply())
cnt++;
else
cnt = INF;
}
res[que.id] = get(que.i);
}
for (ll x : res)
cout << x << "\n";
}
void program() {
input();
sweep();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
program();
return 0;
}
