CF2207H2.Bowser's Castle (Medium Version)

Bowser's Castle Corridor — Shiho Fujii, Ryo Nagamatsu, New Super Mario Bros. Wii

这是本题的中等版本。在本版本中，$n \leq 200$，你最多可以进行 $10^4$ 次询问。只有在你通过了本题所有版本后，才可以进行 Hack。

这是一道交互题。

给定一个正整数 $n$。对于 $n$ 个变量 $x_1, \ldots, x_n$，某个函数被称为“min-max函数”，如果它可以只通过在 $x_1, \ldots, x_n$（每个变量仅出现一次，且顺序与其下标一致）外加 $\min$ 和 $\max$ 操作括起来得到。例如，$\min(x_1, x_2, x_3)$ 是 $3$ 个变量的 min-max 函数，但 $\max(\min(x_1, x_3), x_2)$ 以及 $\min(\max(x_1, x_2), \max(x_2, x_3))$ 都不是。

Bowser 已经选择了一个 $n$ 个变量的 min-max 函数，并把 $n$ 告诉了你。你可以向 Bowser 提出如下询问：给出 $n$ 个整数 $x_1, \ldots, x_n$（$1 \leq x_i \leq 10^9$），他会告诉你 $f(x_1, \ldots, x_n)$ 的值。

为了逃出他的城堡，你需要在最多 $10^4$ 次询问内推断出他的函数。之后，为了证明你已经学会了这个函数，Bowser 会给你最多 $5000$ 个他的输入 $x_1, \ldots, x_n$，你需要输出对应的 $f(x_1, \ldots, x_n)$ 的值。

由于 Bowser 的城堡非常安全，他实际上会让你推断多个函数，所有函数变量总数不超过 $200$。你所有函数的询问总数不能超过 $10^4$，他也不会向你询问超过 $5000$ 次。

每个测试点包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 100$）。
每个测试用例第一行为一个整数 $n$（$2 \leq n \leq 200$），表示 min-max 函数的变量数。

保证所有用例的 $n$ 之和不超过 $200$。

读入该行之后，你就可以进行第一次交互询问了。

在第一个测试用例中，Bowser 的 min-max 函数为 $f := \max(x_1, x_2, x_3)$。当你询问 $f(5, 4, 3) = 5$ 以及 $f(1, 2, 1) = 2$ 后，你可以正确判断对于他的询问 $f(3, 6, 2) = 6$ 及 $f(3, 5, 7) = 7$。

在第二个测试用例中，Bowser 的 min-max 函数为 $f := \min(\max(x_1, x_2), \max(x_3, x_4))$。当你询问 $f(1, 9, 8, 7) = 8$ 以及 $f(5, 10^9, 2, 3) = 3$ 后，你可以正确回答他的 $f(8, 7, 6, 5) = 6$。

注意，样例中的询问无法保证一定能唯一确定 min-max 函数。示例仅用于展示交互流程。示例输入输出中的空行仅为可读性而设，你的代码输出不需要空行。

由 ChatGPT 5 翻译