CF2031F.Penchick and Even Medians

这是一个交互式的问题。

Penchick 刚从澳大利亚的黄金海岸度假回家，却遗忘给他的宠物鸭 Duong Canh 带礼物！或许经过海滩上的深思熟虑设计出的一道有趣题目，是最好的纪念品。

你面临的任务是找出一个长度为 $n$ 的隐藏排列 $p$，其中 $n$ 是偶数。你可以通过以下方式进行查询：

• 选择排列 $p$ 的一个长度为 $4 \le k \le n$ 的子序列（子序列中的元素不必连续）。交互系统会返回该子序列中的两个中位数。

你的任务是在不超过 80 次查询的条件下，找出排列 $p$ 中这两个中位数的索引。

注意：交互系统是固定的，即排列 $p$ 在开始时就已经确定，并不会根据你的查询而改变。

每个测例包含多个测试用例。第一行包含测例数量 $t$ （$1 \le t \le 1000$）。接下来是每个测试用例的描述。

在每个测试用例中，首先是一个整数 $n$ （$6 \le n \le 100$，且为偶数），即隐藏排列 $p$ 的长度。

读取整数 $n$ 后，你应开始与系统进行交互，直到猜出答案，然后再处理下一个测试用例。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

要进行一次查询，按以下格式输出：

• ? k x_1 x_2 ... x_{k-1} x_k （$4 \le k \le n$，$k$ 是偶数，$1 \le x_i \le n$，所有 $x_i$ 互不相同），其中 $k$ 是选择的子序列长度，后面跟随子序列元素的索引。

每次查询后，你会收到一个包含两个整数 $m_1$ 和 $m_2$ 的响应（$1 \le m_1 < m_2 \le n$），表示这个子序列的两个中位数的值。

每个测试用例中可以进行的查询次数最多为 80。

输出最终答案时，请按以下格式：

• ! i_1 i_2 （$1 \le i_1, i_2 \le n$）——这两个数表示两个中位数的索引。

注意，输出的顺序不重要，即满足 $p_{i_1} = \frac{n}{2}$ 和 $p_{i_2} = \frac{n}{2}+1$，或反之亦可。

在每次查询后，记得输出换行符并刷新输出，否则程序可能由于“空闲限制”而失败。

如果在任何交互步骤中读取到 $-1$ 而不是有效数据，说明出现了无效查询或其他错误，你的程序必须立即退出继续执行会导致程序异常。

示例

在第一个测试用例中，隐藏的排列是 $p = [6, 2, 3, 5, 1, 4]$。

1. 第一次查询选择了整个排列，此时的两个中位数是 $3$ 和 $4$。
2. 第二次查询选择了子序列 $3, 6, 1, 5$，返回的中位数是 $3$ 和 $4$。
3. 第三次查询选择了子序列 $3, 6, 2, 5$，返回的中位数是 $2$ 和 $3$。

答案“! 3 6”是有效的，因为 $p_3 = 3$ 且 $p_6 = 4$。

在第二个测试用例中，隐藏的排列是 $p = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]$。

1. 第一次查询选择了子序列 $1, 3, 7, 8, 9, 10$，返回的中位数是 $3$ 和 $4$。
2. 第二次查询选择了子序列 $1, 2, 3, 4, 5, 6, 7, 8$，返回的中位数是 $6$ 和 $7$。

答案“! 5 6”是有效的，因为 $p_5 = 6$ 和 $p_6 = 5$。

本翻译由 AI 自动生成