题目描述

这是一个交互式问题。

有一个长度为 $n$ 的排列 $p^{\ast}$。

某人秘密地选择了两个整数 $l,r$（$1 \le l \le r \le n$），并以如下方式修改了排列：

• 对于每一个满足 $l \le i \le r$ 的下标 $i$，将 $p_i := p_i + 1$。

记 $a$ 为经过上述修改后得到的数组。

给定整数 $n$，表示排列 $p$ 的长度。

你可以进行一次查询，每次可以选择两个整数 $l, r$（$1 \le l \le r \le n$），并查询原始排列 $p[l\dots r]$ 的子数组和，或修改后数组 $a[l\dots r]$ 的子数组和。对于该查询，系统会返回对应的整数和。

你的任务是在不超过 $\mathbf{40}$ 次查询的情况下，找出用来获得 $a$ 的一对 $(l, r)$。

$^{\ast}$ 长度为 $n$ 的排列是一个由 $n$ 个互不相同、且范围在 $1$ 至 $n$ 之间的整数构成的数组。比如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组含有 $4$）。

输入格式

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

每个测试用例第一行为一个整数 $n$（$1 \le n \le 2 \cdot 10^4$），表示排列的长度。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^4$。

输出格式

（本题为交互题，请根据题意与评测机进行交互，输出格式可参看样例，详细交互协议见题意。）

样例

2


3

4

5


4

8

8

9

1 1 2

2 1 2

! 2 2

1 2 4

2 1 3

2 3 4

! 2 4

样例说明

对于第一个测试用例，$p = [3, 1, 2]$，且 $l = 2$，$r = 2$。因此，修改后的数组 $a = [3, 2, 2]$。

因此，查询“$\texttt{1 1 2}$”返回 $p_1 + p_2 = 3 + 1 = 4$。查询“$\texttt{2 1 2}$”返回 $a_1 + a_2 = 3 + 2 = 5$。

对于第二个测试用例，$p = [2, 1, 3, 4]$，且 $l = 2$, $r = 4$。

注意，样例测试中给出的查询只是为了演示说明，并不一定对应最佳解法。

由 ChatGPT 5 翻译

来源

Codeforces 2162D，英文题名 Beautiful Permutation。