CF1856D.More Wrong

This is an interactive problem.

The jury has hidden a permutation$^\dagger$ $p$ of length $n$.

In one query, you can pick two integers $l$ and $r$ ($1 \le l \lt r \le n$) by paying $(r - l)^2$ coins. In return, you will be given the number of inversions$^\ddagger$ in the subarray $[p_l, p_{l + 1}, \ldots p_r]$.

Find the index of the maximum element in $p$ by spending at most $5 \cdot n^2$ coins.

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

$^\dagger$ 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).

$^\ddagger$ The number of inversions in an array is the number of pairs of indices $(i,j)$ such that $i \lt j$ and $a_i \gt a_j$. For example, the array $[10,2,6,3]$ contains $4$ inversions. The inversions are $(1,2),(1,3),(1,4)$, and $(3,4)$.

这是一个交互式问题。

评测机隐藏了一个长度为 $n$ 的排列$^\dagger$ $p$。

每次查询中，你可以选择两个整数 $l$ 和 $r$（满足 $1 \le l \lt r \le n$），花费 $(r - l)^2$ 枚硬币。作为回应，你将获得子数组 $[p_l, p_{l + 1}, \ldots, p_r]$ 中的逆序对数量$^\ddagger$。

请在总花费不超过 $5 \cdot n^2$ 枚硬币的前提下，找出 $p$ 中最大元素的下标。

注意：评测机是非自适应的，即该排列在任何查询开始前就已固定。

$^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

$^\ddagger$ 数组中的逆序对数量，是指满足 $i \lt j$ 且 $a_i \gt a_j$ 的下标对 $(i,j)$ 的个数。例如，数组 $[10,2,6,3]$ 包含 $4$ 个逆序对，它们分别是 $(1,2)$、$(1,3)$、$(1,4)$ 和 $(3,4)$。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($2 \le n \le 2000$) — the length of the hidden permutation $p$.

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

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例仅有一行，包含一个整数 $n$（$2 \le n \le 2000$），表示隐藏排列 $p$ 的长度。

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

In the first test, the interaction proceeds as follows:

Solution

Jury

Explanation

2

There are $2$ test cases.

4

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

? 1 3

1

The solution requests the number of inversions in the subarray $[1,3,2]$ by paying $4$ coins, and the jury responds with $1$.

? 3 4

0

The solution requests the number of inversions in the subarray $[2,4]$ by paying $1$ coin, and the jury responds with $0$.

! 4

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

2

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

? 1 2

1

The solution requests the number of inversions in the subarray $[2,1]$ by paying $1$ coin, and the jury responds with $1$.

! 1

The solution has somehow determined that $p_1 = 2$, 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.

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

程序

裁判

说明

2

共有 $2$ 个测试用例。

4

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

? 1 3

1

程序通过支付 $4$ 枚硬币，请求子数组 $[1,3,2]$ 中的逆序对数量，裁判回应结果为 $1$。

? 3 4

0

程序通过支付 $1$ 枚硬币，请求子数组 $[2,4]$ 中的逆序对数量，裁判回应结果为 $0$。

! 4

程序以某种方式确定了 $p_4 = 4$，并输出该值。由于输出正确，裁判继续处理下一个测试用例。

2

在第二个测试用例中，隐藏的排列为 $[2,1]$，长度为 $2$。

? 1 2

1

程序通过支付 $1$ 枚硬币，请求子数组 $[2,1]$ 中的逆序对数量，裁判回应结果为 $1$。

! 1

程序以某种方式确定了 $p_1 = 2$，并输出该值。由于输出正确且已无更多测试用例，裁判与程序均退出。

注意：示例输入与输出中的换行仅为便于理解，在实际交互中并不存在换行。