We have the following property:

• If \(A_l\gt A_r\), then \(f(l,r)\lt A\).
• If \(A_l= A_r\), then \(f(l,r)= A\).
• If \(A_l\lt A_r\), then \(f(l,r)\gt A\).

Therefore, if we define \(X\) as the number of pairs \((l,r)\) with \(A_l\lt A_r\) and \(Y\) as the number of pairs \((l,r)\) with \(A_l\gt A_r\):

• If \(1\leq k\leq X\), then \(B_k\lt A\).
• If \(X\lt k\lt \frac{N(N-1)}{2}-Y\), then \(B_k= A\).
• If \(\frac{N(N-1)}{2}-Y\leq k\leq \frac{N(N-1)}{2}\), then \(B_k\gt A\).

Consider the case where \(k\leq X\). For \((l_1,r_1)\) and \((l_2, r_2)\) such that \(A_{l_1}\gt A_{r_1}\) and \(A_{l_2}\gt A_{r_2}\), the ordering between \(f(l_1,r_1)\) and \(f(l_2,r_2)\) matches the ordering between \((l_1,A_{r_1},-r_1)\) and \((l_2,A_{r_2},-r_2)\).

---

Proof

Without loss of generality, assume that \((l_1,r_1)\lt (l_2,r_2)\).

• If \(l_1\lt l_2\)
  The first \((l_1-1)\) terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are the same, while the \(l_1\)-th terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are \(A_{r_1}\ (\lt A_{l_1})\) and \(A_{l_1}\), respectively. Thus, \(f(l_1,r_1)\lt f(l_2,r_2)\).

• If \(l_1= l_2\) and \(A_{r_1}\neq A_{r_2}\)
  The first \((l_1-1)\) terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are the same, while the \(l_1\)-th terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are \(A_{r_1}\) and \(f(l_2,r_2)\), respectively. Thus, the ordering between \(f(l_1,r_1)\) and \(f(l_2,r_2)\) coincides with the ordering between \(A_{r_1}\) and \(A_{r_2}\).

• If \(l_1= l_2\) and \(A_{r_1}= A_{r_2}\). In this case, \(r_1\lt r_2\). The first \((r_1-1)\) terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are equal, while the \(r_1\)-th terms of \(f(l_1,r_1)\) and \(f(l_2,r_2)\) are \(A_{l_1}\) and \(A_{r_1}\). Thus, \(f(l_1,r_1)\gt f(l_2,r_2)\).

Putting together the three cases above, we assert that the ordering between \(f(l_1,r_1)\) and \(f(l_2,r_2)\) matches the ordering between \((l_1,A_{r_1},-r_1)\) and \((l_2,A_{r_2},-r_2)\).

---

Based on this fact, \((l,r)\) can be determined by the following steps:

1. Find \(l\).
2. Find the value of \(A_r\).
3. Find \(r\).

1. Finding \(l\)

For each \(i\), if we denote by \(c_i\) the number of indices \(j\) with \(A_i\gt A_j\ (i\lt j)\), the sought \(l\) is the one that satisfies \(c_1+c_2+\ldots + c_{l-1}\lt k\leq c_1+c_2+\ldots + c_l\).

2. Finding the value of \(A_r\)

Let \(k' = k-(c_1+c_2+\ldots + c_{l-1})\). Let \(S\) be a multiset of \(A_j\) for all \(j\) with \(A_l\gt A_j\ (l\lt j)\). Then \(A_r\) is the \(k'\) smallest element of \(S\).

3. Finding \(r\)

Let \(v\) be the value of \(A_r\) found in the step above. Let \(m\) be the number of elements in \(S\) smaller than \(v\), and \(k''=k'-m\). Then \(r=I_{k''}\), where \(I\) is the sequence of indices \(j\ (l\lt j)\) with \(A_j\) in descending order.

---

If there are many queries with \(k\leq X\), the answers can be found in ascending order of \(k\). To process the second step fast, we can use data structures like Fenwick Tree, segment tree, or a set that supports retrieval of the \(k\)-th minimum value.

(Alternatively, one can define a set structure that maintains integer pairs and supports \(k\)-th minimum value retrieval, and manage \((A_r,-r)\) to process steps 2 and 3 at once.)

Cases with \(B_k\gt A\) can be handled in the same way. For For \((l_1,r_1)\) and \((l_2, r_2)\) such that \(A_{l_1}\lt A_{r_1}\) and \(A_{l_2}\lt A_{r_2}\), the ordering between \(f(l_1,r_1)\) and \(f(l_2,r_2)\) matches the ordering between \((-l_1,A_{r_1},r_1)\) and \((-l_2,A_{r_2},r_2)\). Cases with \(B_k=A\) are trivial to handle.

The writer’s solution runs in a total of \(O(Q\log Q + (N+Q)\log N)\) time.

#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";
  }
}