#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
/** Does not work with 0-based indexing */
class fenwick_tree {
private:
int n;
vector<int> fenw;
#ifdef DEBUG
vector<int> debug;
#endif
public:
fenwick_tree() {}
fenwick_tree(int _n) : n(_n) {
fenw.assign(n, 0);
#ifdef DEBUG
debug.assign(n, 0);
#endif
}
/** Updates fenw[idx] to x. Gets stuck in infinite loop if idx = 0 */
void update(int idx, int x) {
#ifdef DEBUG
debug[idx] += x;
#endif
while (idx < n) {
fenw[idx] += x;
idx += (idx & -idx);
}
}
/** Returns sum of all elements in fenw[1..idx]. Returns 0 if idx = 0 */
int query(int idx) {
int ans = 0;
while (idx > 0) {
ans += fenw[idx];
idx -= (idx & -idx);
}
return ans;
}
/** Returns smallest idx such that fenw[idx] >= x. Returns n if there is no such element. Assumes all current elements are nonnegative */
int lower_bound(int x) {
int idx = 0, cur = 0;
for (int i = ceil(log2(n + 1)); i >= 0; i--) {
if (idx + (1 << i) < n && cur + fenw[idx + (1 << i)] < x) {
idx += (1 << i);
cur += fenw[idx];
}
}
return idx + 1;
}
};
int n, q;
bool start = true, stopped = false;
vector<int> a, next_larger;
map<int, pair<int, int> > blocks;
fenwick_tree fenw;
void init_deck() {
int prev = 0;
for (int i = 1; i < n / 2; i++) {
if (a[i] > a[prev]) {
blocks[a[prev]] = {prev, i - 1};
prev = i;
}
}
blocks[a[prev]] = {prev, n / 2 - 1};
prev = n / 2;
for (int i = n / 2 + 1; i < n; i++) {
if (a[i] > a[prev]) {
blocks[a[prev]] = {prev, i - 1};
prev = i;
}
}
blocks[a[prev]] = {prev, n - 1};
for (auto &p : blocks) fenw.update(p.first, p.second.second - p.second.first + 1);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (st.empty()) next_larger[i] = INF;
else next_larger[i] = st.top();
st.push(i);
}
}
void shuffle_cards() {
if (stopped) return;
if (start) {
init_deck();
start = false;
return;
}
int mid = fenw.lower_bound(n / 2 + 1);
int l = fenw.query(mid - 1);
if (l == n / 2) {
stopped = true;
return;
}
int l_idx = blocks[mid].first + n / 2 - l;
for (int i = l_idx; i <= blocks[mid].second; i = next_larger[i]) {
blocks[a[i]] = {i, min(next_larger[i] - 1, blocks[mid].second)};
fenw.update(a[i], min(next_larger[i] - 1, blocks[mid].second) - i + 1);
}
fenw.update(mid, l_idx - 1 - blocks[mid].second); blocks[mid].second = l_idx - 1;
}
int get_card(int idx) {
if (start) return a[idx - 1];
int block = fenw.lower_bound(idx);
return a[blocks[block].first + idx - fenw.query(block - 1) - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector< tuple<int, int, int> > queries;
for (int i = 0; i < q; i++) {
int t, idx;
cin >> t >> idx;
queries.push_back({t, idx, i});
}
sort(queries.begin(), queries.end());
int cur = 0;
vector<int> ans(q);
fenw = fenwick_tree(n + 1);
next_larger.resize(n);
for (auto &p : queries) {
int t = get<0>(p), idx = get<1>(p);
for (; cur < t; cur++) shuffle_cards();
ans[get<2>(p)] = get_card(idx);
}
for (auto &x : ans) cout << x << '\n';
return 0;
}
