/*
start thinking:
BULB:
result of thinking: Pure.

start coding:
AC:
*/
#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
template<class T1, class T2> bool chmin(T1 &x, const T2 &y) {
  return x > y ? (x = y, true) : false;
}
template<class T1, class T2> bool chmax(T1 &x, const T2 &y) {
  return x < y ? (x = y, true) : false;
}
bool Mbe;

#define maxn 200005
#define maxq 1000005
int n, q, a[maxn], nxt[maxn], stk[maxn], tp, ans[maxq], pos[maxn];
vector<P> qs[maxn]; // (pos, id)

int bit[maxn];

void add(int p, int x) {
  for (int i = p; i <= n; i += i & -i)
    bit[i] += x;
}
int qsum(int p) {
  int res = 0;
  for (int i = p; i; i -= i & -i)
    res += bit[i];
  return res;
}
int kth(int &k) {
  int res = 0;
  for (int i = 17; i >= 0; i--) {
    if ((res + (1 << i)) <= n && bit[res + (1 << i)] < k) {
      res += 1 << i;
      k -= bit[res];
    }
  }
  return res + 1;
}

bool Med;
int main() {
  fprintf(stderr, "%.2fMB\n", (&Mbe - &Med) / 1048576.);
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    pos[a[i]] = i;
  }
  for (int i = 1; i <= q; i++) {
    int t, j;
    scanf("%d%d", &t, &j);
    qs[min(t, n)].emplace_back(j, i);
  }
  for (int i = n; i >= 1; i--) {
    while (tp && a[i] > a[stk[tp]])
      tp--;
    if (!tp)
      nxt[i] = n + 1;
    else
      nxt[i] = stk[tp];
    stk[++tp] = i;
  }
  for (int i = 1; i <= n; i = nxt[i])
    add(a[i], nxt[i] - i);
  for (int i = 0; i <= n; i++) {
    for (auto j : qs[i]) {
      int foo = kth(j.first);
      ans[j.second] = a[pos[foo] + j.first - 1];
    }
    int mid = n / 2 + 1;
    int foo = kth(mid);
    if (mid == 1)
      continue;
    int fooLen = qsum(foo) - qsum(foo - 1), ed = pos[foo] + fooLen;
    add(foo, mid - 1 - fooLen);
    for (int j = pos[foo] + mid - 1; j < ed; j = nxt[j]) {
      add(a[j], min(ed, nxt[j]) - j);
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
  cerr << "time: " << clock() << "ms" << endl;
  return 0;
}

Main idea: greedily divide the permutation into disjoint ranges, so that the first element in each range is greater than the rest of the elements (call such ranges valid). For example, with the sample we have

Note that the first elements of the ranges must be sorted in increasing order. Then, in each move:

• If the two middle elements are in different ranges, nothing will happen, and the permutation will stay the same.
• Otherwise, we cut the range in the space between these two elements. The left portion is still valid, while the right portion might not be - we divide this range greedily into smaller valid ranges. Because the ranges in both the left half and right half are now sorted by the first element, the deck after the riffle shuffle will have all ranges sorted by first element.

If we maintain the set of integers that are the first elements of a range, along with the range sizes, it's possible to get the kth element in the permutation in $O(\log n)$ with something like a Fenwick tree. This allows us to both get the $$$(\frac{n}{2} + 1)^\text{th}$$$ element (necessary for splitting the ranges) and answer the queries.

Single tree, $$$Q = K - 1$$$: choose any $$$K$$$ nodes, sort them by preorder, then ask queries about consecutive pairs (v1, v2), (v2, v3), (v3, v4), ..., (v[k-1], v[k]). You should also find lca(v1, v2), lca(v2, v3), lca(v3, v4), and so on. All of that is enough to know all the distances that you need.

Two trees, $$$Q = K - 1$$$: greedily choose the first $$$K$$$ nodes encountered by DFS in the first tree. Then focus on the second tree and apply the logic from before. The answers that you get turn out to be enough in the first tree too — because your nodes form a connected component including the root, and any LCA is one of the chosen nodes too.