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 自动生成**

In the first test case, the hidden permutation is $ p = [6, 2, 3, 5, 1, 4] $ . 1. The entire permutation was chosen for the first query. The two medians of the entire permutation $ p $ are $ 3 $ and $ 4 $ . 2. The indices of the chosen subsequence in the second query are $ 3 $ , $ 6 $ , $ 1 $ , and $ 5 $ . The interactor returns the two medians of the subsequence $ [p_3, p_6, p_1, p_5] = [3, 4, 6, 1] $ , which are $ 3 $ and $ 4 $ . 3. The indices of the chosen subsequence in the second query are $ 3 $ , $ 6 $ , $ 2 $ , and $ 5 $ . The interactor returns the two medians of the subsequence $ [p_3, p_6, p_2, p_5] = [3, 4, 2, 1] $ , which are $ 2 $ and $ 3 $ . The answer "! 3 6" is valid as $ p_3 = 3 $ and $ p_6 = 4 $ . In the second test case, the hidden permutation is $ p = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] $ . 1. The indices of the chosen subsequence in the second query are $ 1 $ , $ 3 $ , $ 7 $ , $ 8 $ , $ 9 $ , and $ 10 $ . The interactor returns the two medians of the subsequence $ [p_1, p_3, p_7, p_8, p_9, p_{10}] = [10, 8, 4, 3, 2, 1] $ , which are $ 3 $ and $ 4 $ . 2. The indices of the chosen subsequence in the second query are $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ , $ 7 $ , and $ 8 $ . The interactor returns the two medians of the subsequence $ [p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8] = [10, 9, 8, 7, 6, 5, 4, 3] $ , which are $ 6 $ and $ 7 $ . The answer "! 5 6" is valid as $ p_5 = 6 $ and $ p_6 = 5 $ .