CF1698D.Fixed Point Guessing

This is an interactive problem.

Initially, there is an array $a = [1, 2, \ldots, n]$, where $n$ is an odd positive integer. The jury has selected $\frac{n-1}{2}$ disjoint pairs of elements, and then the elements in those pairs are swapped. For example, if $a=[1,2,3,4,5]$, and the pairs $1 \leftrightarrow 4$ and $3 \leftrightarrow 5$ are swapped, then the resulting array is $[4, 2, 5, 1, 3]$.

As a result of these swaps, exactly one element will not change position. You need to find this element.

To do this, you can ask several queries. In each query, you can pick two integers $l$ and $r$ ($1 \leq l \leq r \leq n$). In return, you will be given the elements of the subarray $[a_l, a_{l + 1}, \dots, a_r]$ sorted in increasing order.

Find the element which did not change position. You can make at most $\mathbf{15}$ queries.

The array $a$ is fixed before the interaction and does not change after your queries.

Recall that an array $b$ is a subarray of the array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

这是一个交互式问题。

初始时，存在一个数组 $a = [1, 2, \ldots, n]$，其中 $n$ 是一个正奇数。评测系统已选定 $\frac{n-1}{2}$ 个互不相交的元素对，并将每对中的两个元素交换位置。例如，若 $a=[1,2,3,4,5]$，且交换了元素对 $1 \leftrightarrow 4$ 和 $3 \leftrightarrow 5$，则得到的数组为 $[4, 2, 5, 1, 3]$。

经过这些交换后，恰好有一个元素的位置保持不变。你需要找出这个元素。

为此，你可以提出若干次查询。每次查询中，你可指定两个整数 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$）。作为回应，你将收到子数组 $[a_l, a_{l + 1}, \dots, a_r]$ 的所有元素按升序排列后的结果。

请找出那个位置未发生改变的元素。你最多可进行 $\mathbf{15}$ 次查询。

数组 $a$ 在交互开始前即已固定，且在你进行查询的过程中不会发生变化。

注意：若数组 $b$ 可通过从数组 $a$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到，则称 $b$ 是 $a$ 的一个子数组。

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3 \leq n \lt 10^4$; $n$ is odd) — the length of the array $a$.

After reading the first line of each test case, you should begin the interaction.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \lt 10^4$；且 $n$ 为奇数），表示数组 $a$ 的长度。

在读取每个测试用例的第一行后，你应开始交互。

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

In the first test, the interaction proceeds as follows.

Solution

Jury

Explanation

$\texttt{2}$

There are 2 test cases.

$\texttt{5}$

In the first test case, the hidden array is $[4,2,5,1,3]$, with length $5$.

$\texttt{? 1 4}$

$\texttt{1 2 4 5}$

The solution requests the subarray $[4,2,5,1]$ in increasing order, and the jury responds with $[1,2,4,5]$.

$\texttt{? 3 5}$

$\texttt{1 3 5}$

The solution requests the subarray $[5,1,3]$ in increasing order, and the jury responds with $[1,3,5]$.

$\texttt{! 2}$

The solution has somehow determined that $a_2=2$, and outputs it. Since the output is correct, the jury continues to the next test case.

$\texttt{3}$

In the second test case, the hidden array is $[1,3,2]$, with length $3$.

$\texttt{? 1 1}$

$\texttt{1}$

The solution requests the number $[1]$ only, and the jury responds with $[1]$.

$\texttt{! 1}$

The solution has determined that $a_1=1$, and outputs it. Since the output is correct and there are no more test cases, the jury and the solution exit.

Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.

在第一个测试用例中，交互过程如下所示。

解法

出题方

说明

$\texttt{2}$

共有 2 个测试用例。

$\texttt{5}$

在第一个测试用例中，隐藏数组为 $[4,2,5,1,3]$，长度为 $5$。

$\texttt{? 1 4}$

$\texttt{1 2 4 5}$

解法请求子数组 $[4,2,5,1]$ 的升序排列，出题方回应 $[1,2,4,5]$。

$\texttt{? 3 5}$

$\texttt{1 3 5}$

解法请求子数组 $[5,1,3]$ 的升序排列，出题方回应 $[1,3,5]$。

$\texttt{! 2}$

解法以某种方式确定了 $a_2=2$，并输出该值。由于输出正确，出题方继续处理下一个测试用例。

$\texttt{3}$

在第二个测试用例中，隐藏数组为 $[1,3,2]$，长度为 $3$。

$\texttt{? 1 1}$

$\texttt{1}$

解法仅请求单个元素 $[1]$，出题方回应 $[1]$。

$\texttt{! 1}$

解法确定了 $a_1=1$，并输出该值。由于输出正确且已无更多测试用例，出题方与解法程序退出。

注意：示例输入与输出中的换行仅为清晰起见，在实际交互中并不会出现。