CF2022D2.Asesino (Hard Version)

这是该问题的困难版本。在本版本中，你必须使用尽可能少的询问次数。只有在两个版本都被解决的情况下，你才能进行 Hack。

这是一个交互式问题。

在墨西哥国家 IOI 集训中，有一个传统游戏叫做“Asesino”，它类似于“Among Us”或“Mafia”。

今天，有 $n$ 名玩家（编号从 $1$ 到 $n$）将参与“Asesino”游戏，游戏中有以下三种角色：

• 骑士（Knight）：骑士总是说真话。
• 恶棍（Knave）：恶棍总是说谎。
• 冒名顶替者（Impostor）：冒名顶替者表面上被所有人认为是骑士，实际上却是恶棍。

每个玩家都会被分配一个角色。游戏中恰好有一名冒名顶替者，但骑士和恶棍的人数可以为任意（可能为零）。

作为游戏主持人，你不小心忘记了每个人的角色，但你需要确定谁是冒名顶替者。

为了找出冒名顶替者，你可以提出一些问题。每次提问，你可以选择两个玩家 $i$ 和 $j$（$1 \leq i, j \leq n$，$i \neq j$），并询问玩家 $i$ 是否认为玩家 $j$ 是骑士。问题的回答规则如下表所示：

	骑士（Knight）	恶棍（Knave）	冒名顶替者（Impostor）
骑士	是	否	是
恶棍	否	是	否
冒名顶替者	否	是	—

表中第 $a$ 行第 $b$ 列的回答表示当 $i$ 的角色为 $a$，$j$ 的角色为 $b$ 时的回答。例如，第一行第三列的“是”表示当 $i$ 是骑士，$j$ 是冒名顶替者时的回答是“是”。

请用最少的询问次数找出冒名顶替者。也就是说，设 $f(n)$ 为对于 $n$ 个玩家，存在一种策略最多用 $f(n)$ 次询问就能确定冒名顶替者。你必须在不超过 $f(n)$ 次询问内确定冒名顶替者。

注意：评测器是自适应的：玩家的角色在一开始并未固定，可能会根据你的提问动态变化。但保证始终存在一种角色分配方式，使得所有已提问的问题都满足本题的约束。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 10^5$），表示参与游戏的人数。

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

每次提问时，输出一行，格式如下：

• "? i j"（$1 \leq i, j \leq n$，$i \neq j$）——表示询问玩家 $i$ 是否认为玩家 $j$ 是骑士。

评测器会返回 "1" 表示玩家 $i$ 认为玩家 $j$ 是骑士，返回 "0" 表示不是。

当你确定了冒名顶替者是谁时，输出一行，格式如下：

• "! i"（$1 \leq i \leq n$）——表示第 $i$ 位玩家是冒名顶替者。

注意，输出答案不计入 $f(n)$ 次询问的限制。

如果你的输出不合法、询问次数超过 $f(n)$ 或者错误地确定了冒名顶替者，评测器会返回 "-1"，你的程序必须立即终止。否则，你的程序可能会因为读取已关闭的流而收到任意判题结果。

每次输出询问后，别忘了输出换行并刷新输出缓冲区。否则，你会因“Idleness limit exceeded”而被判为超时。具体刷新方法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Python：sys.stdout.flush()
• Rust：stdiostdout().flush()
• 其它语言请参见相关文档。

Hack 格式

对于 Hack，请使用如下格式。

第一行包含一个整数 $t$，表示测试用例数量。

每个测试用例的第一行包含整数 $n$ 和字符串 "manual"。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \leq a_i \leq 1$），表示每个玩家的角色。$1$ 表示骑士，$0$ 表示恶棍，$-1$ 表示冒名顶替者。必须恰好有一个 $a_i = -1$。

例如，Hack 输入格式如下：

2
7 manual
0 1 0 -1 0 1 0
4 manual
0 1 -1 0

注意，示例测试用例并不代表最优的提问策略，仅用于演示交互格式。实际上，通过示例中的提问无法确定冒名顶替者。

在第一个测试用例中，第 $2$ 和第 $6$ 位玩家是骑士，第 $1$、$3$、$5$、$7$ 位玩家是恶棍，第 $4$ 位玩家是冒名顶替者。以下是各次提问的解释：

• 第一次提问，$i$ 是恶棍，$j$ 是恶棍。回答为“是”，因为恶棍总是说谎。
• 第二次提问，$i$ 是恶棍，$j$ 是骑士。回答为“否”，因为恶棍总是说谎。
• 第三次提问，$i$ 是骑士，$j$ 是恶棍。回答为“否”，因为骑士总是说真话。
• 第四次提问，$i$ 是骑士，$j$ 是骑士。回答为“是”，因为骑士总是说真话。
• 第五次提问，$i$ 是冒名顶替者，$j$ 是恶棍。回答为“是”，因为冒名顶替者总是说谎。
• 第六次提问，$i$ 是冒名顶替者，$j$ 是骑士。回答为“否”，因为冒名顶替者总是说谎。
• 第七次提问，$i$ 是恶棍，$j$ 是冒名顶替者。回答为“否”，因为恶棍总是说谎，并且恶棍认为冒名顶替者是骑士。

由 ChatGPT 4.1 翻译