A16679 | Beautiful Permutation

这是一个交互式问题。

有一个长度为 $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$。

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