310591: CF1856D. More Wrong

D. More Wrongtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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$.

Interaction

The interaction for each test case begins by reading the integer $n$.

To make a query, output "? l r" ($1 \le l < r \le n$) without quotes. Afterwards, you should read one single integer — the answer for your query.

If you receive the integer $-1$ instead of an answer or a valid value of $n$, it means your program has made an invalid query, has exceed the limit of queries, or has given an incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "! i" ($1 \le i \le n$) without quotes — the index of the maximum of the hidden permutation. After solving a test case, your program should move to the next one immediately. After solving all test cases, your program should be terminated immediately.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

To hack, use the following format:

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.

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

The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ($1 \le p_i \le n$), $p$ must be a permutation.

The sum of $n$ over all test cases should not exceed $2000$.

ExampleInput

2
4

1

0

2

1

Output

? 1 3

? 3 4

! 4

? 1 2

! 1

Note

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.

题目大意：
这是一个交互式问题。评委会隐藏了一个长度为n的排列p。你可以通过支付(r - l)^2个硬币来选择两个整数l和r（1 ≤ l < r ≤ n），并得到子数组[p_l, p_{l + 1}, … p_r]中逆序对的数量。在花费不超过5 * n^2个硬币的情况下，找到排列p中最大元素的索引。

注意：评分器不是自适应的：在提出任何查询之前，排列是固定的。

输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行输入包含一个整数t（1 ≤ t ≤ 100）——测试用例的数量。
每个测试用例的唯一一行包含一个整数n（2 ≤ n ≤ 2000）——隐藏排列p的长度。
保证所有测试用例的n之和不超过2000。

输出：
对于每个测试用例，交互开始于读取整数n。
要提出查询，输出"? l r"（1 ≤ l < r ≤ n）而不加引号。之后，你应该读取一个整数——对你查询的答案。
如果你收到整数-1而不是答案或有效的n值，这意味着你的程序提出了无效查询，超过了查询限制，或在上一个测试用例中给出了错误答案。你的程序必须立即终止，以获得错误答案的判断。否则，你可能会得到任意判断，因为你的解决方案将继续从已关闭的流中读取。
准备好给出最终答案时，输出"! i"（1 ≤ i ≤ n）而不加引号——隐藏排列中最大值的索引。解决一个测试用例后，你的程序应立即进入下一个。解决所有测试用例后，你的程序应立即终止。

在打印查询后不要忘记输出换行符并刷新输出。否则，你会得到“空闲限制超出”。为此，使用：
- 在C++中：fflush(stdout)或cout.flush()；
- 在Java中：System.out.flush()；
- 在Pascal中：flush(output)；
- 在Python中：stdout.flush()；
- 查看其他语言的文档。

示例：
输入：
2
4

1

0

2

1

输出：
? 1 3

? 3 4

! 4

? 1 2

! 1

注意：示例输入和输出中的换行符是为了清晰起见，实际交互中不会出现。题目大意： 这是一个交互式问题。评委会隐藏了一个长度为n的排列p。你可以通过支付(r - l)^2个硬币来选择两个整数l和r（1 ≤ l < r ≤ n），并得到子数组[p_l, p_{l + 1}, … p_r]中逆序对的数量。在花费不超过5 * n^2个硬币的情况下，找到排列p中最大元素的索引。 注意：评分器不是自适应的：在提出任何查询之前，排列是固定的。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行输入包含一个整数t（1 ≤ t ≤ 100）——测试用例的数量。 每个测试用例的唯一一行包含一个整数n（2 ≤ n ≤ 2000）——隐藏排列p的长度。 保证所有测试用例的n之和不超过2000。 输出： 对于每个测试用例，交互开始于读取整数n。 要提出查询，输出"? l r"（1 ≤ l < r ≤ n）而不加引号。之后，你应该读取一个整数——对你查询的答案。 如果你收到整数-1而不是答案或有效的n值，这意味着你的程序提出了无效查询，超过了查询限制，或在上一个测试用例中给出了错误答案。你的程序必须立即终止，以获得错误答案的判断。否则，你可能会得到任意判断，因为你的解决方案将继续从已关闭的流中读取。 准备好给出最终答案时，输出"! i"（1 ≤ i ≤ n）而不加引号——隐藏排列中最大值的索引。解决一个测试用例后，你的程序应立即进入下一个。解决所有测试用例后，你的程序应立即终止。 在打印查询后不要忘记输出换行符并刷新输出。否则，你会得到“空闲限制超出”。为此，使用： - 在C++中：fflush(stdout)或cout.flush()； - 在Java中：System.out.flush()； - 在Pascal中：flush(output)； - 在Python中：stdout.flush()； - 查看其他语言的文档。 示例： 输入： 2 4 1 0 2 1 输出： ? 1 3 ? 3 4 ! 4 ? 1 2 ! 1 注意：示例输入和输出中的换行符是为了清晰起见，实际交互中不会出现。