1856D · More Wrong

Problem: 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 < 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 < j$ and $a_i > 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)$.

Input Format: 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$.

Note: In the first test, the interaction proceeds as follows:

SolutionJuryExplanation2There are $2$ test cases.4In the first test case, the hidden permutation is $[1,3,2,4]$, with length $4$.? 1 3 1The solution requests the number of inversions in the subarray $[1,3,2]$ by paying $4$ coins, and the jury responds with $1$.? 3 4 0The 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.2In the second test case, the hidden permutation is $[2,1]$, with length $2$.? 1 2 1The 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.