如果我们将 \(a\) 数组从大到小排序，那么显然的，前 \(k\) 个数就对应着长度为 \(k\) 的元素和最大的子序列中各元素的值。
由于要求字典序最小，所以我们将 \(a\) 数组中的元素下标进行排序，在排序时以对应的元素值为第一关键字，以元素下标为第二关键字（排序后对应的元素值从大到小，大小相等的元素，下标更小的在前）。我们称排序后得到的数组为 \(b\)。
那么这时我们就可以发现，\(b\) 数组里前 \(k\) 个元素对应的就是 \(a\) 数组中，长度为 \(k\) 的 optimal subsequence 中的各元素下标。
因此，\(b\) 数组前 \(k\) 个中第 \(p\) 小的元素对应的那个元素，就是长度为 \(k\) 的 optimal subsequence 中第 \(p\) 个元素。
那么这时问题就转化成了“找到 \(b\) 数组前 \(k\) 个元素中第 \(p\) 小的那个”。
这时就可以用主席树解决了，但是我不想码主席树，所以我把询问存下来，按 \(k\) 排序，离线回答。
具体的回答方法是，开一棵 pbds 的平衡树，遍历询问，如果 \(k\) 变大了，就向平衡树中添加 \(b\) 中元素直至平衡树大小为 \(k\)，然后树中第 \(p\) 小的元素即是答案元素的下标。
时间复杂度 \(O(n\log n)\)。
代码：
#include<bits/extc++.h>
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
constexpr int N = 2e5 + 5;
int n, m, a[N], b[N], ans[N];
struct query {
int k, p, id;
bool operator<(const query& b) const {
return k < b.k;
}
}q[N];
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
iota(b + 1, b + n + 1, 1);
sort(b + 1, b + n + 1, [](int i, int j)
{ return a[i] == a[j] ? i < j : a[i] > a[j]; });
cin >> m;
for(int i = 1; i <= m; ++i) cin >> q[i].k >> q[i].p, q[i].id = i;
sort(q + 1, q + m + 1);
for(int i = 1, j = 0; i <= m; ++i) {
while(j < q[i].k) tr.insert(b[++j]);
ans[q[i].id] = a[*tr.find_by_order(q[i].p - 1)];
}
for(int i = 1; i <= m; ++i) cout << ans[i] << endl;
return 0;
}