G-寻找'0'

题目描述

这是一个交互题。如果你从未写过，请查看题目最后注意事项。

给定一个整数 $n$。存在一个长度为 $2n$ 的隐藏数组 $a$。从 $1$ 到 $n$ 的每个整数在 $a$ 中都恰好出现一次，其余元素均为 $0$。

你可以进行如下类型的查询：

• 选择两个整数 $i$ 和 $j$（$1 \le i, j \le 2n$，$i \ne j$），裁判会回应 $1$，如果 $a_i = a_j$，否则回应 $0$。
• 使用? i j向交互器询问，如果你找到了答案，请使用! x告知交互器并停止程序。

请在不超过 $n+1$ 次查询内，找到任意一个满足 $a_k=0$ 的整数 $k$（$1 \le k \le 2n$）。注意交互方是自适应的，这意味着隐藏数组 $a$ 可能会根据你的查询动态变化，但不会违反之前的查询结果。

当找到结果但程序未停止，或超出查询限制时，交互器将返回0分。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^3$）。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^4$）。隐藏数组 $a$ 的长度为 $2n$。

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

输出格式

（交互题，无需输出格式固定说明。）

输入输出样例 #1

输入 #1

2
2

0

1

3

1

0

0

输出 #1

? 1 2

? 3 1

! 3

? 5 6

? 2 4

? 1 3

! 6

说明/提示

在第一个示例测试用例中，隐藏数组 $a$ 为 $[0,1,0,2]$：

• 第一次查询，$(i, j) = (1,2)$。由于 $a_1=0$，$a_2=1$，$a_1 \ne a_2$，裁判回应 $0$。
• 第二次查询，$(i, j) = (3,1)$。由于 $a_3=0$，$a_1=0$，$a_3 = a_1$，裁判回应 $1$。
• 程序报告 $k=3$ 作为答案。由于 $a_3=0$，答案正确。

在第二个示例测试用例中，隐藏数组 $a$ 为 $[3,2,0,1,0,0]$：

• 第一次查询，$(i, j) = (5,6)$。由于 $a_5=0$，$a_6=0$，$a_5 = a_6$，裁判回应 $1$。
• 第二次查询，$(i, j) = (2,4)$。由于 $a_2=2$，$a_4=1$，$a_2 \ne a_4$，裁判回应 $0$。
• 第三次查询，$(i, j) = (1,3)$。由于 $a_1=3$，$a_3=0$，$a_1 \ne a_3$，裁判回应 $0$。
• 程序报告 $k=6$ 作为答案。由于 $a_6=0$，答案正确
• 。

交互题注意事项

对于这类题目，只需像往常一样将询问写到标准输出，刷新输出缓冲 后从标准输入读取结果。

选手程序刷新输出缓冲后，通过管道连接它的测评程序（称为交互器）才能立刻接收到这些数据。

因为如果你输出了一些数据，这些数据可能被放置于内部缓存区里，而且或许没有被直接传输给 interactor。

为了避免这种情况的发生，你需要每次输出时用一种特殊的清除缓存操作。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。