/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
using T3 = tuple<int, int, int>;
const ll mod = 998244353;
const ll INF = 1LL << 60;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)
template<class T> bool chmin(T &a, T b) {
if (a > b) {
a = b; return 1;
}
return 0;
}
template<class T> bool chmax(T &a, T b) {
if (a < b) {
a = b; return 1;
}
return 0;
}
template<class T> void print(vector<T> a) {
int n = a.size();
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
class BIT {
public:
vector<int> dat; int siz = 0;
void init(int n) {
dat.assign(n + 1, 0); siz = n;
}
void add(int pos, int x) {
//cerr << "add " << pos << " " << x << endl;
while (pos <= siz) {
dat[pos] += x; pos += pos & -pos;
}
}
int sum(int pos) {
int ret = 0;
while (pos > 0) {
ret += dat[pos]; pos -= pos & -pos;
}
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void set(int pos, int x) {
add(pos, x - sum(pos, pos));
}
// 総和がvを超えない最大のインデックス
int min_left(int v) {
int pos = 0, cur = 0;
for (int i = 29; i >= 0; i--) {
if ((1<<i) + pos > siz) continue;
if (cur + dat[pos + (1<<i)] < v) {
cur += dat[pos + (1<<i)]; pos += (1<<i);
}
}
return pos;
}
};
const ll MAX = 3e5;
ll f(T3 p) {
return get<0>(p) * MAX * MAX + get<1>(p) * MAX + get<2>(p);
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<T3> query(q);
rep(i, q) {
cin >> get<0>(query[i]) >> get<1>(query[i]);
get<2>(query[i]) = i;
}
sort(query.begin(), query.end());
stack<int> st;
vector<int> nex(n, n); // 自分以降で最初の自分より大きいカードの添え字
rep(i, n) {
while (!st.empty() && a[st.top()] < a[i]) {
nex[st.top()] = i; st.pop();
}
st.push(i);
}
priority_queue<T3> cur, total, removed;
int pos = 0, numca = n;
while (pos < n) {
cur.push({a[pos], pos, nex[pos]-1});
total.push({a[pos], pos, nex[pos]-1});
pos = nex[pos];
}
// 1回目のシミュレーション
int simu = n + 10;
while (simu-- && numca > n / 2) {
while (1) {
if (numca == n / 2) break;
auto [v, l, r] = cur.top(); cur.pop();
if (numca - n / 2 >= r - l + 1) {
numca -= r - l + 1; removed.push({v, l, r}); continue;
}
numca -= r - l + 1;
int pos = l + n/2 - numca;
cur.push({v, l, pos - 1}); numca = n/2;
total.push({v, l, pos - 1});
while (pos <= r) {
cur.push({a[pos], pos, nex[pos]-1});
total.push({a[pos], pos, nex[pos]-1});
numca += nex[pos] - pos;
pos = nex[pos];
}
break;
}
}
BIT bit; bit.init(total.size());
unordered_map<ll, int> rev;
vector<T3> lis;
while (!total.empty()) {
rev[f(total.top())] = total.size();
lis.push_back(total.top());
total.pop();
}
lis.push_back({0, 0, 0}); reverse(lis.begin(), lis.end());
/*rep(i, lis.size()) {
cerr << "lis[" << i << "] = " << get<0>(lis[i]) << " " << get<1>(lis[i]) << " " << get<2>(lis[i]) << endl;
}*/
while (!cur.empty()) cur.pop();
pos = 0, numca = n;
while (pos < n) {
//cerr << "! " << pos << " " << a[pos] << " " << nex[pos] << endl;
cur.push({a[pos], pos, nex[pos]-1});
bit.add(rev[f({a[pos], pos, nex[pos]-1})], nex[pos] - pos);
pos = nex[pos];
}
int shu = 0;
vector<int> memo(q); // カードの添え字を格納
for (auto [t, id, qid] : query) {
while (shu < t) {
// シャッフルをする
while (1) {
if (numca == n / 2) break;
auto [v, l, r] = cur.top(); cur.pop();
if (numca - n / 2 >= r - l + 1) {
numca -= r - l + 1; continue;
}
bit.add(rev[f({v, l, r})], -(r - l + 1));
numca -= r - l + 1;
int pos = l + n/2 - numca;
cur.push({v, l, pos - 1}); numca = n/2;
bit.add(rev[f({v, l, pos-1})], pos - l);
while (pos <= r) {
cur.push({a[pos], pos, nex[pos]-1});
bit.add(rev[f({a[pos], pos, nex[pos]-1})], nex[pos] - pos);
numca += nex[pos] - pos;
pos = nex[pos];
}
break;
}
shu++;
}
int p0 = bit.min_left(id);
memo[qid] = get<1>(lis[p0+1]) - 1 + id - bit.sum(p0);
//cerr << "memo " << qid << " " << memo[qid] << endl;
}
rep(i, q) cout << a[memo[i]] << endl;
}
