CF2168B.Locate

This is a run-twice (communication) interactive problem.

There are two players: Player A and Player B. The jury (otherwise known as the interactor of this problem) will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information to or receive information from the jury.

Before the interaction, the jury determines an integer $n$ and a permutation $p$$^{\text{∗}}$ of the integers from $1$ to $n$ exactly once. These values are consistent across both players.

Player A receives the value of $n$ and all elements of $p$ from the jury. Then, Player A must send a binary integer $x$ (that is, $x$ must equal $0$ or $1$) back to the jury.

Player B receives the value of $n$ and the integer $x$ (the same integer that player A sent) from the jury. However, the permutation $p$ is not given to player B. Player B's task is to determine the position of integer $n$ in $p$. To do so, Player B can ask the jury at most $30$ queries in the following form:

• Choose any two integers $l$ and $r$ ($l \leq r$) and the jury will respond with $\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$.

Player A wants to ensure that player B can determine the position of $n$. Your task is to act as both players and determine an optimal interaction strategy for both players so that player B determines the position of $n$ correctly.

First Run

Your code will run exactly twice on each test. On the first run, you will be Player A.

Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Player A.

The second line of the input contains exactly one integer $t$ — the number of test cases ($1 \le t \le 100$).

The first line of the $i$-th test case contains an integer $n$ — the length of $p$ for the $i$-th test case ($2 \le n \le 10^4$).

The second line of the $i$-th test case contains $n$ space-separated integers $p_1, p_2, \ldots, p_n$. It is guaranteed this sequence forms a permutation.

It is guaranteed the sum of $n$ over all test cases does not exceed $10^4$.

Output

For each test case, print an integer $x$, either $0$ or $1$, on a new line. This is the integer that will be sent to you in the second run.

After this, proceed to the next test case, or you terminate your program if it was the last test case.

Second Run

On the second run, you are Player B.

Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Player B.

The second line of the input contains exactly one integer $t$ — the number of test cases ($1 \le t \le 100$). Note that this number is equal to $t$ from the first run input.

The first line of each test case contains two integers $n$ and $x$ ($2 \leq n \leq 10^4$, $0 \leq x \leq 1$). This denotes the length of $p$ and the binary integer $x$ that was sent by Player A from the last run.

Note that the test cases in the second run may be shuffled. Please see the example test case for further illustration.

Interaction

For the $i$-th test case, recall you will first receive $n$ and $x$ in the input from the jury according to the input format above. After receiving those inputs, you will be able to make at most $30$ queries of the following form (ignore quotes):

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

After each query, the jury will respond with $\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$, in which you should read through the input stream.

If your program makes more than $30$ queries, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Once you are ready to report the position of $n$, you may do so in the following format:

• ! P ($1 \leq P \leq n$), where $P$ is the position of $n$.

Then, you will either proceed to the next test case, or your program must terminate if you have processed every test case.

The interactor is not adaptive. That is, the permutation will not change during the interaction, and will always be the same permutation as shown to you in the first run.

After printing each query do not forget to output the end of line and flush$^{\text{†}}$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^{\text{†}}$To flush, use:

• fflush(stdout) or cout.flush() in C++;
• sys.stdout.flush() in Python;
• see the documentation for other languages.

这是一个需运行两次的（通信）交互式问题。

共有两名玩家：玩家 A 和玩家 B。评测系统（即本题的交互器）将首先与玩家 A 进行交互；在玩家 A 的交互结束后，评测系统再与玩家 B 进行交互。注意，玩家 A 与玩家 B 不能直接互相传递信息；双方都只能向评测系统发送信息，或从评测系统接收信息。

在交互开始前，评测系统会确定一个整数 $n$ 和一个 $1$ 到 $n$ 的排列 $p^{\text{∗}}$（每个整数恰好出现一次）。这些值在两名玩家之间保持一致。

玩家 A 从评测系统处接收 $n$ 的值以及排列 $p$ 的全部元素。随后，玩家 A 必须向评测系统返回一个二进制整数 $x$（即 $x$ 只能为 $0$ 或 $1$）。

玩家 B 从评测系统处接收 $n$ 的值以及整数 $x$（即玩家 A 所发送的同一个整数），但不会获得排列 $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$ —— 第 $i$ 个测试用例中排列 $p$ 的长度（$2 \le n \le 10^4$）。

第 $i$ 个测试用例的第二行包含 $n$ 个以空格分隔的整数 $p_1, p_2, \ldots, p_n$。保证该序列构成一个排列。

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

输出

对每个测试用例，在一行中输出一个整数 $x$（仅限 $0$ 或 $1$）。该整数将在第二次运行时提供给你。

输出后，继续处理下一个测试用例；若已处理完全部测试用例，则终止程序。

第二次运行

在第二次运行中，你将作为玩家 B。

输入

输入的第一行包含字符串 second，用于提示你的程序：本次为第二次运行，应以玩家 B 的身份执行。

输入的第二行包含一个整数 $t$ —— 测试用例的数量（$1 \le t \le 100$）。注意，该数值与第一次运行输入中的 $t$ 相同。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$2 \leq n \leq 10^4$，$0 \leq x \leq 1$），分别表示排列 $p$ 的长度以及玩家 A 在上一轮运行中所发送的二进制整数 $x$。

注意：第二次运行中的测试用例顺序可能被打乱。请参见样例测试用例以进一步理解。

交互方式

对于第 $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（其中 $1 \leq P \leq n$，$P$ 即为 $n$ 在 $p$ 中的位置）

然后，你将进入下一个测试用例；若已处理完全部测试用例，则必须终止程序。

本交互器为非自适应型（non-adaptive），即整个交互过程中排列 $p$ 不会发生变化，且始终与第一次运行中展示给你的排列完全相同。

每次输出查询后，请务必输出换行符并刷新输出缓冲区$^{\text{†}}$；否则你将收到“空闲超限”（Idleness limit exceeded）判据。

若在任意交互步骤中，你读取到 $-1$ 而非有效数据，你的程序必须立即退出。这意味着你的解法因非法查询或其他错误而被判为“答案错误”。未及时退出可能导致任意判据（因程序将继续从已关闭的输入流中读取数据）。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的 $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()；
• 其他语言请查阅相应文档。

For the first run: The permutations $[3,2,1]$, $[1,2,3,4,5]$, $[4,2,3,5,1]$ are given. According to some strategy between the players, the integers $0$, $0$, and $1$ are sent respectively.

For the second run: Note that the test cases are re-ordered between runs. This time, the permutations are given in the order $[3,2,1]$, $[4,2,3,5,1]$,$[1,2,3,4,5]$. However, note that the integer $x$ for each test case is the same as what is given in the first run (that is, $0,1,0$).

Consider the first permutation of the second run. The permutation is $p = [3, 2, 1]$.

In the first query, player B asks for the difference between the maximum and the minimum among $p_1, p_2, p_3$. The judge answers with $2$ ($p = [3, 2, 1]$, so $\max(p_1, p_2, p_3) - \min(p_1, p_2, p_3) = 3 - 1 = 2$).

Likewise, the judge answers with $1$ on both the second and the third queries player B makes. Then, player B, using both the queries he made, as well as the integer player A has chosen, figures out that the integer $n$ ($n = 3$) can be found at position $1$ of the permutation. This is correct, as $p_1 = 3$.

第一次运行：给定排列 $[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]$，所以 $\max(p_1, p_2, p_3) - \min(p_1, p_2, p_3) = 3 - 1 = 2$）。

类似地，裁判对玩家 B 进行的第二和第三次查询均回答 $1$。随后，玩家 B 结合自己所作的全部查询以及玩家 A 所选定的整数，推断出整数 $n$（即 $n = 3$）位于该排列的第 $1$ 个位置。该结论正确，因为 $p_1 = 3$。