CF1584D.Guess the Permutation

This is an interactive problem.

Jury initially had a sequence $a$ of length $n$, such that $a_i = i$.

The jury chose three integers $i$, $j$, $k$, such that $1 \leq i \lt j \lt k \leq n$, $j - i \gt 1$. After that, Jury reversed subsegments $[i, j - 1]$ and $[j, k]$ of the sequence $a$.

Reversing a subsegment $[l, r]$ of the sequence $a$ means reversing the order of elements $a_l, a_{l+1}, \ldots, a_r$ in the sequence, i. e. $a_l$ is swapped with $a_r$, $a_{l+1}$ is swapped with $a_{r-1}$, etc.

You are given the number $n$ and you should find $i$, $j$, $k$ after asking some questions.

In one question you can choose two integers $l$ and $r$ ($1 \leq l \leq r \leq n$) and ask the number of inversions on the subsegment $[l, r]$ of the sequence $a$. You will be given the number of pairs $(i, j)$ such that $l \leq i \lt j \leq r$, and $a_i \gt a_j$.

Find the chosen numbers $i$, $j$, $k$ after at most $40$ questions.

The numbers $i$, $j$, and $k$ are fixed before the start of your program and do not depend on your queries.

这是一个交互式问题。

评测组最初有一个长度为 $n$ 的序列 $a$，满足 $a_i = i$。

评测组选择了三个整数 $i$、$j$、$k$，满足 $1 \leq i \lt j \lt k \leq n$ 且 $j - i \gt 1$。随后，评测组对序列 $a$ 的两个子段 $[i, j - 1]$ 和 $[j, k]$ 分别执行了翻转操作。

对序列 $a$ 的子段 $[l, r]$ 进行翻转，是指将元素 $a_l, a_{l+1}, \ldots, a_r$ 的顺序反转，即 $a_l$ 与 $a_r$ 交换，$a_{l+1}$ 与 $a_{r-1}$ 交换，依此类推。

你将获得整数 $n$，需通过提出若干询问来确定 $i$、$j$、$k$ 的值。

每次询问中，你可以选择两个整数 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$），并查询序列 $a$ 在子段 $[l, r]$ 上的逆序对数量。你将得到满足 $l \leq i \lt j \leq r$ 且 $a_i \gt a_j$ 的数对 $(i, j)$ 的个数。

你需要在至多 $40$ 次询问内找出所选的 $i$、$j$、$k$。

数字 $i$、$j$、$k$ 在你的程序开始运行前即已固定，且不依赖于你提出的任何询问。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. Description of the test cases follows.

The single line of each test case contains a single integer $n$ ($4 \leq n \leq 10^9$). After reading it you should start an interaction process by asking questions for that test case. After giving an answer you should:

• Terminate your program if that is the last test case.
• Proceed to the next test case otherwise.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅占一行，包含一个整数 $n$（$4 \leq n \leq 10^9$）。读入该数后，你需要针对该测试用例启动交互过程并提出问题。在给出答案后，你应当：

• 若这是最后一个测试用例，则终止你的程序；
• 否则，继续处理下一个测试用例。

In the first test case, $i = 1$, $j = 3$, $k = 5$, so the sequence $a$ is $[2, 1, 5, 4, 3]$.

In the second test case, $i = 2$, $j = 4$, $k = 5$, so the sequence $a$ is $[1, 3, 2, 5, 4]$.

在第一个测试用例中，$i = 1$，$j = 3$，$k = 5$，因此序列 $a$ 为 $[2, 1, 5, 4, 3]$。

在第二个测试用例中，$i = 2$，$j = 4$，$k = 5$，因此序列 $a$ 为 $[1, 3, 2, 5, 4]$。