题目描述

Tom 写了一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，里面是 $n$ 个互不相同的整数，每个都在 $1$ 到 $10^9$ 之间。33DAI 看不到这些数，他只能向 Tom 提一个问题：比较两个位置上的数哪个更小。

33DAI 想知道：第 $k$ 小的那个数在哪个位置。请你帮他问出来，并且问的次数要尽量少。

本题是函数式交互题。你不需要写 main 函数，只要实现下面两个函数（在随题下发的 kth.h 里声明）。你的源文件里必须写上 #include "kth.h"，否则无法编译。

void init(int t, int n);
long long kth(int k);

• init(t, n)：每个测试点开始时调用一次。$t$ 是这个测试点里数组的组数，$n$ 是每组的长度（相同）。
• kth(k)：返回当前这一组里第 $k$ 小元素所在的位置（$1$ 到 $n$ 的整数），即满足 $a_p$ 是第 $k$ 小值的下标 $p$。由于所有数互不相同，这个位置是唯一的。每组的询问次数从 $0$ 开始计。

你可以调用下面这个函数向评测程序提问：

int compare(int i, int j);

• 比较第 $i$ 个与第 $j$ 个数的大小，要求 $1 \le i, j \le n$ 且 $i \ne j$：
  • 返回 $1$ 表示 $a_i < a_j$；
  • 返回 $0$ 表示 $a_i > a_j$。

除了比较，没有任何办法读出一个位置上的数值。

评分方式：记 $M$ 为"这个测试点里，某一组问得最多的次数"。

• 只要有任何一组答错，本测试点得 $0$ 分；
• $M \le 6n$ 得满分（快速选择的期望询问次数约为 $3n$）；
• $6n < M < 60n$ 时分数从满分线性降到 $0$；$M \ge 60n$ 得 $0$ 分。 （把整组排序需要约 $n\log_2 n \approx 10n$ 次比较，只能拿到部分分。）

输入格式

本题没有传统意义上的输入文件：数据由评测程序（grader）读入，你只要实现上面两个函数。

随题下发的文件（见「附加文件」）：

• kth.h：接口声明；
• grader.cpp：示例评测程序，只用来在本地把你的程序跑起来；
• compile.sh：编译脚本。

本地编译命令（把你自己的代码保存为 foo.cc，与上面三个文件放在同一个目录）：

g++ -o foo foo.cc grader.cpp -O2 -std=c++14

示例 grader 的本地输入格式是：第一行两个整数 $t, n$；之后 $t$ 行每行 $n$ 个数（这一组数组的值），再之后 $t$ 行每行一个 $k$。

注意：示例 grader 只用于本地自测，它的数据格式、数据范围与判分方式都和正式评测不同； 正式评测使用另一份 grader，请以题面写明的接口与规则为准。

输出格式

不需要输出任何东西：kth() 的返回值就是答案，由评测程序收集。

样例

某个测试点里 $t = 2$、$n = 4$，两组数组分别是 $[40, 10, 30, 20]$ 与 $[7, 9, 8, 6]$。

第一组要问 $k = 2$（第 $2$ 小的数在哪个位置）：

你的程序                评测程序
compare(2, 1)  ->       1        （a2 = 10 < a1 = 40）
compare(2, 3)  ->       1        （a2 = 10 < a3 = 30）
compare(2, 4)  ->       1        （a2 = 10 < a4 = 20，说明 a2 是最小的）
compare(4, 3)  ->       1        （a4 = 20 < a3 = 30）
compare(4, 1)  ->       1        （a4 = 20 < a1 = 40，说明 a4 是第 2 小的）
kth(2) 返回 4

数组排序后是 $10 < 20 < 30 < 40$，第 $2$ 小的数 $20$ 在位置 $4$，所以答案是 $4$ —— 注意它既不是 $1$ 也不是 $k$。

第二组 $k = 3$：数组是 $[7, 9, 8, 6]$，排序后是 $6 < 7 < 8 < 9$，第 $3$ 小的数 $8$ 在位置 $3$，所以 kth(3) 返回 $3$。

提示

• 本题是函数式交互题：kth.h、grader.cpp、compile.sh 随题下发，你只提交实现 init / kth 的源文件。
• 同一个数组里元素互不相同，所以 compare 不会返回"相等"，你不需要处理相等的情况。
• 把整组排序就能解决，但要 $O(n\log n)$ 次比较，拿不到满分；想想怎样只用 $O(n)$ 次比较就定出第 $k$ 小。
• 同一组数据里每组的询问次数单独统计，最后取最大的那个。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 20$；
• $2 \le n \le 1000$；
• 每组内的 $n$ 个整数互不相同，且都在 $[1, 10^9]$ 内；
• $1 \le k \le n$。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点计分。