CFCF2168B.Locate

这是一个双轮（通信）交互题。

有两名玩家：玩家 A 和玩家 B。评测机（即本题的交互器）会先与玩家 A 进行交互。在玩家 A 完成交互后，评测机会与玩家 B 进行交互。注意，玩家 A 和玩家 B 不能直接传递信息；他们只能通过与评测机进行通信来实现信息的传递。

在交互开始之前，评测机会选定一个整数 $n$，以及一个长度为 $n$ 的排列 $p$ $^{\text{∗}}$，排列为 $1$ 到 $n$ 的某种顺序。这些数值在两位玩家之间均保持一致。

玩家 A 会收到 $n$ 和排列 $p$ 的全部元素。接着，玩家 A 必须向评测机发送一个二进制整数 $x$（即 $x$ 只能是 $0$ 或 $1$）。

玩家 B 会获得 $n$ 和从评测机得到的整数 $x$（即玩家 A 发送的整数），但玩家 B 不知道排列 $p$。玩家 B 的任务是确定整数 $n$ 在排列 $p$ 中的位置。为此，玩家 B 最多可以向评测机发起 $30$ 次询问，询问的形式为：

• 选择任意两个整数 $l$ 和 $r$（$l \leq r$），评测机会回复 $\max(p_l, p_{l+1}, \ldots, p_r) - \min(p_l, p_{l+1}, \ldots, p_r)$。

玩家 A 希望玩家 B 能确定 $n$ 的具体位置。你的任务是分别作为两位玩家，设计一种最优的交互策略，使玩家 B 能正确确定 $n$ 的位置。

第一次运行

你的代码会在每个测试点上运行两次。第一次运行时，你扮演玩家 A。

输入

第一行输入字符串 first，指示本次为第一次运行，你应以玩家 A 的身份作答。

第二行输入一个整数 $t$，表示测试用例数（$1 \le t \le 100$）。

第 $i$ 个测试用例的第一行输入一个整数 $n$，表示本次排列 $p$ 的长度（$2 \le n \le 10^4$）。

第 $i$ 个测试用例的第二行输入 $n$ 个由空格分隔的整数 $p_1, p_2, \ldots, p_n$，保证这些数形成一个长度为 $n$ 的排列。

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

输出

对于每个测试用例，在新的一行输出一个整数 $x$，其值为 $0$ 或 $1$。这是将会在第二次运行时收到的整数。

完成本测试用例后，继续进入下一个测试用例；若为最后一个测试用例则应终止程序。

第二次运行

第二次运行时，你扮演玩家 B。

输入

第一行输入字符串 second，指示本次为第二次运行，你应以玩家 B 的身份作答。

第二行输入一个整数 $t$，表示测试用例数（$1 \le t \le 100$），该值与第一次运行输入相同。

每组测试数据的第一行输入两个整数 $n$ 和 $x$（$2 \leq n \leq 10^4$，$0 \leq x \leq 1$），分别表示排列 $p$ 的长度与玩家 A 发送的二进制整数。

注意，第二次运行时，测试用例的顺序可能与第一次不同。参见输入输出示例获得更详细的说明。

交互过程

对于第 $i$ 个测试用例，你将获得 $n$ 和 $x$。接下来，你最多可以向评测机发起 $30$ 次以下格式的询问（无需引号）：

• ? l r ($1 \leq l \leq r \leq n$)

询问后，评测机会回复 $\max(p_l, p_{l+1}, \ldots, p_r) - \min(p_l, p_{l+1}, \ldots, p_r)$ 的值，你需要通过输入流读取。

如果你的程序发起了超过 $30$ 次询问，你应立即终止程序，否则会收到 Wrong Answer 判罚。其他判罚也可能发生，因为此时你的程序会继续从已关闭的流中读取数据，导致未知行为。

当你准备好报告 $n$ 在排列 $p$ 中的位置时，按照以下格式输出：

• ! P（$1 \leq P \leq n$），其中 $P$ 为 $n$ 在 $p$ 中的位置。

完成所有测试用例后必须终止程序。

交互过程中，别忘了输出每次询问后加上换行，并刷新输出流 $^{\text{†}}$，否则会收到 Idleness limit exceeded 判罚。

如果任何交互步骤中你读入 $-1$ 而不是有效数据，必须立刻退出。这说明你的解因非法询问或其他错误被评测机判错。未退出可能会导致未知判罚，因为你的程序仍然会从已关闭的流读取数据。

$^{\text{∗}}$ 长度为 $n$ 的排列是包含 $1$ 到 $n$ 所有整数且各不相同的数组。例如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，却有 $4$）。

$^{\text{†}}$ 刷新输出流示例：

• 在 C++ 中用 fflush(stdout) 或 cout.flush()；
• 在 Python 中用 sys.stdout.flush()；
• 其他语言请查阅相关文档。

略（见题目描述中“输入”部分）。

略（见题目描述中“输出”部分及交互过程）。

对于第一次运行：给定的排列为 $[3,2,1]$、$[1,2,3,4,5]$、$[4,2,3,5,1]$。根据玩家的某种策略，发送的整数分别为 $0$、$0$、$1$。

对于第二次运行：注意测试用例顺序被重新排列，此时排列为 $[3,2,1]$、$[4,2,3,5,1]$、$[1,2,3,4,5]$。但每个测试用例中发送的整数 $x$ 与第一次运行时一致（即 $0,1,0$）。

例如第二次运行的第一个排列为 $p = [3,2,1]$。

第一次询问，玩家 B 询问 $p_1, p_2, p_3$ 的最大值和最小值差，评测机回复 $2$（$p = [3,2,1]$，所以 $3-1=2$）。

同样，玩家 B 对第 $2$ 和第 $3$ 次区间询问得到的也是 $1$。玩家 B 通过自己的所有询问和玩家 A 的整数 $x$，可以推出整数 $n$（即 $3$）所在排列的位置为第 $1$ 位。因为 $p_1 = 3$。