CF2207H3.Bowser's Castle (Hard Version)

Final Boss Phase 2 (Lava) / Giant Bowser — Shiho Fujii, Ryo Nagamatsu, New Super Mario Bros. Wii

本题为该问题的难度加强版。不同版本的区别在于，本题中 $n\leq 400$，你可以进行最多 $1500$ 次询问。只有在你通过了所有版本后才能进行 hack。

本题为交互题。

给定一个正整数 $n$。一个 $n$ 变量的函数 $f(x_1,\ldots,x_n)$ 被称为“min-max 函数”，当且仅当它可以只用 $\min$ 和 $\max$，并且每个变量 $x_1, x_2, \ldots, x_n$ 恰好出现一次，且按顺序从左到右嵌套在表达式中构造出来。例如，$\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)$ 的值。

为了逃出他的城堡，你需要在总共不超过 $1500$ 次询问内，推断出他的这个函数；推断完毕后，为了向 Bowser 证明你已经学会了这个函数，他会给你最多 $5000$ 组由他选定的 $x_1, \ldots, x_n$，你需要输出每一组的 $f(x_1,\ldots,x_n)$ 的值。

由于 Bowser 的城堡非常安全，实际上他准备了多组函数让你找，总变量数不超过 $400$。你询问的总次数不超过 $1500$，他也不会询问超过 $5000$ 次。

每个测试点包含多组样例。
第一行包含一个正整数 $t$（$1 \leq t \leq 200$），表示测试用例的个数。

每组样例的第一行有一个正整数 $n$（$2 \leq n \leq 400$），表示 min-max 函数的变量个数。

保证所有测试用例的 $n$ 之和不超过 $400$。

读取到每组样例的这一行输入后，交互即开始，你可以进行第一次询问。

（本题为交互题，具体交互及输出格式需根据题面中的要求实现）

在第一个样例中，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 翻译