CF2162D.Beautiful Permutation

This is an interactive problem.

There is a permutation$^{\text{∗}}$ $p$ of length $n$.

Someone secretly chose two integers $l, r$ ($1 \le l \le r \le n$) and modified the permutation in the following way:

• For every index $i$ such that $l \le i \le r$, set $p_i := p_i + 1$.

Let $a$ denote the resulting array obtained by modifying the permutation.

You are given an integer $n$ denoting the length of the permutation $p$.

In one query, you are allowed to choose two integers $l, r$ ($1 \le l \le r \le n$) and ask for the sum of the subarray either of the original permutation $p[l \dots r]$ or of the modified array $a[l \dots r]$. The answer to such a query will be the corresponding integer sum.

Your task is to find the pair $(l, r)$ that was chosen to obtain $a$ in no more than $\bf{40}$ queries.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$).

这是一个交互式问题。

存在一个长度为 $n$ 的排列$^{\text{∗}}$ $p$。

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

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

记 $a$ 为对排列 $p$ 修改后所得的数组。

你将获得一个整数 $n$，表示原始排列 $p$ 的长度。

在一次查询中，你可以任选两个整数 $l, r$（满足 $1 \le l \le r \le n$），并询问原始排列 $p[l \dots r]$ 的子数组和，或修改后数组 $a[l \dots r]$ 的子数组和。该查询的返回值即为对应的整数和。

你的任务是在不超过 $\bf{40}$ 次查询内，确定用于得到 $a$ 的那对 $(l, r)$。

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

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^4$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^4$.

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

每个测试用例包含一个整数 $n$（$1 \le n \le 2\cdot10^4$）—— 排列的长度。

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

For the first testcase, $p = [3, 1, 2]$ and $l = 2$, $r = 2$. Hence, the modified array $a$ will be equal to $[3, 2, 2]$.

So, querying "$\texttt{1 1 2}$" gives $p_1 + p_2 = 3 + 1 = 4$. And querying "$\texttt{2 1 2}$" gives $a_1 + a_2 = 3 + 2 = 5$.

For the second testcase, $p = [2, 1, 3, 4]$ and $l = 2$, $r = 4$.

Note that the queries shown in the sample test are only for demonstration purposes, and they may not correspond to any optimal solution.

对于第一个测试用例，$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$。

注意：样例测试中展示的查询仅用于演示目的，它们未必对应任何最优解。