以下が成り立ちます．

• \(A_l\gt A_r\) ならば \(f(l,r)\lt A\)
• \(A_l= A_r\) ならば \(f(l,r)= A\)
• \(A_l\lt A_r\) ならば \(f(l,r)\gt A\)

よって，\(A_l\lt A_r\) となる \((l,r)\) の個数を \(X\)，\(A_l\gt A_r\) となる \((l,r)\) の個数を \(Y\) とすると，

• \(1\leq k\leq X\) なら \(B_k\lt A\)
• \(X\lt k\lt \frac{N(N-1)}{2}-Y\) なら \(B_k= A\)
• \(\frac{N(N-1)}{2}-Y\leq k\leq \frac{N(N-1)}{2}\) なら \(B_k\gt A\)

です．

\(k\leq X\) の場合について考えます．\(A_{l_1}\gt A_{r_1}, A_{l_2}\gt A_{r_2}\) であるような \((l_1,r_1), (l_2, r_2)\) について，\(f(l_1,r_1)\) と \(f(l_2,r_2)\) の大小は \((l_1,A_{r_1},-r_1)\) と \((l_2,A_{r_2},-r_2)\) の大小に一致します．

---

証明

一般性を失わず \((l_1,r_1)\lt (l_2,r_2)\) とします．

• \(l_1\lt l_2\) の場合
  \(f(l_1,r_1)\) と \(f(l_2,r_2)\) は \(l_1-1\) 項目までは等しく，\(f(l_1,r_1)\) の \(l_1\) 項目は \(A_{r_1}\ (\lt A_{l_1})\)，\(f(l_2,r_2)\) の \(l_1\) 項目は \(A_{l_1}\) です．よって \(f(l_1,r_1)\lt f(l_2,r_2)\) です．

• \(l_1= l_2\) かつ \(A_{r_1}\neq A_{r_2}\) の場合
  \(f(l_1,r_1)\) と \(f(l_2,r_2)\) は \(l_1-1\) 項目までは等しく，\(f(l_1,r_1)\) の \(l_1\) 項目は \(A_{r_1}\)，\(f(l_2,r_2)\) の \(l_1\) 項目は \(A_{r_2}\) であるため，\(f(l_1,r_1)\) と \(f(l_2,r_2)\) の大小は \(A_{r_1}\) と \(A_{r_2}\) の大小に一致します．

• \(l_1= l_2\) かつ \(A_{r_1}= A_{r_2}\) の場合
  このとき \(r_1\lt r_2\) です．\(f(l_1,r_1)\) と \(f(l_2,r_2)\) は \(r_1-1\) 項目までは等しく，\(f(l_1,r_1)\) の \(r_1\) 項目は \(A_{l_1}\)，\(f(l_2,r_2)\) の \(r_1\) 項目は \(A_{r_1}\) です．よって \(f(l_1,r_1)\gt f(l_2,r_2)\) です．

以上の \(3\) つの場合分けをまとめると，\(f(l_1,r_1)\) と \(f(l_2,r_2)\) の大小は \((l_1,A_{r_1},-r_1)\) と \((l_2,A_{r_2},-r_2)\) の大小に一致することが言えます．

---

これを踏まえると，\((l,r)\) を

1. \(l\) を決定する
2. \(A_r\) の値を決定する
3. \(r\) を決定する

の順番に求めることができます．

1. \(l\) の決定

各 \(i\) に対して，\(A_i\gt A_j\ (i\lt j)\) となる \(j\) の個数を \(c_i\) とすると，求めたい \(l\) は \(c_1+c_2+\ldots + c_{l-1}\lt k\leq c_1+c_2+\ldots + c_l\) を満たすような \(l\) です．

2. \(A_r\) の値の決定

\(k' = k-(c_1+c_2+\ldots + c_{l-1})\) とします．多重集合 \(S\) を \(A_l\gt A_j\ (l\lt j)\) であるような \(j\) 全てに対する \(A_j\) の集合とします．このとき \(A_r\) は \(S\) の中で \(k'\) 番目に小さい要素です．

3. \(r\) の決定

2 で決定した \(A_r\) の値を \(v\) とします．2 の \(S\) において，\(v\) より小さい値の個数を \(m\) ，\(k''=k'-m\) とします．\(A_j = v\) となるような \(j\ (l\lt j)\) を 降順 に並べた列を \(I\) とすると，\(r=I_{k''}\) です．

---

\(k\leq X\) のクエリがたくさんある場合には，\(k\) の昇順に答えを求めていくことができます．\(2\) 番目の処理が高速に行えるように fenwick tree や segment tree，kth min が取得できる set などを用いると良いです．

（別の方法として，kth min が取得できるような整数の \(2\) つ組を扱う set を用意して，集合で \((A_r,-r)\) を管理することで 2 と 3 の処理を同時に行っても良いです．）

同様の方法で \(B_k\gt A\) の場合も処理できます．\(A_{l_1}\lt A_{r_1}, A_{l_2}\lt A_{r_2}\) であるような \((l_1,r_1), (l_2, r_2)\) について，\(f(l_1,r_1)\) と \(f(l_2,r_2)\) の大小は \((-l_1,A_{r_1},r_1)\) と \((-l_2,A_{r_2},r_2)\) の大小に一致します．\(B_k=A\) の場合の処理は簡単です．

想定解の計算量は全体で \(O(Q\log Q + (N+Q)\log N)\) です．

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ll long long

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<pair<ll, int>> query;
  for (int i = 0; i < q; i++) {
    ll k;
    cin >> k;
    query.push_back({k - 1, i});
  }

  sort(query.rbegin(), query.rend());
  vector<pair<int, int>> ans(q);

  ordered_set<pair<int, int>> S;
  for (int i = 0; i < n; i++) {
    S.insert({a[i], -i});
  }

  // B_k < A
  ll cnt = 0;
  for (int l = 0; l < n; l++) {
    S.erase({a[l], -l});
    ll lim = S.order_of_key({a[l], -(1 << 30)});
    while (!query.empty()) {
      auto [k, qi] = query.back();

      ll k1 = k - cnt;
      if (k1 < lim) {
        ans[qi] = {l, -(*S.find_by_order(k1)).second};
        query.pop_back();
      } else {
        break;
      }
    }
    cnt += lim;
  }

  // B_k = A
  {
    vector<int> C(n + 1, 0), idx(n + 1, -1);
    pair<int, int> p;
    for (int i = 0; i < n; i++) {
      if (idx[a[i]] != -1) {
        p = {idx[a[i]], i};
      }
      cnt += C[a[i]];
      C[a[i]]++;
      idx[a[i]] = i;
    }
    while (!query.empty()) {
      auto [k, qi] = query.back();
      if (k < cnt) {
        ans[qi] = p;
        query.pop_back();
      } else {
        break;
      }
    }
  }

  // B_k > A
  for (int l = n - 1; l >= 0; l--) {
    int offset = S.order_of_key({a[l], 1 << 30});
    while (!query.empty()) {
      auto [k, qi] = query.back();
      int k1 = k - cnt + offset;
      if (k1 < S.size()) {
        ans[qi] = {l, (*S.find_by_order(k1)).second};
        query.pop_back();
      } else {
        break;
      }
    }
    cnt += S.size() - offset;
    S.insert({a[l], l});
  }

  for (auto [l, r] : ans) {
    cout << l + 1 << " " << r + 1 << "\n";
  }
}