CF1526F.Median Queries

This is an interactive problem.

There is a secret permutation $p$ ($1$-indexed) of numbers from $1$ to $n$. More formally, for $1 \leq i \leq n$, $1 \leq p[i] \leq n$ and for $1 \leq i \lt j \leq n$, $p[i] \neq p[j]$. It is known that $p[1] \lt p[2]$.

In $1$ query, you give $3$ distinct integers $a,b,c$ ($1 \leq a,b,c \leq n$), and receive the median of ${|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|}$.

In this case, the median is the $2$-nd element ($1$-indexed) of the sequence when sorted in non-decreasing order. The median of ${4,6,2}$ is $4$ and the median of ${0,123,33}$ is $33$.

Can you find the secret permutation in not more than $2n+420$ queries?

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

这是一个交互式问题。

存在一个秘密排列 $p$（从 $1$ 开始编号），其元素为 $1$ 到 $n$ 的整数。更准确地说，对所有 $1 \leq i \leq n$，满足 $1 \leq p[i] \leq n$；且对所有 $1 \leq i < j \leq n$，满足 $p[i] \neq p[j]$。已知 $p[1] < p[2]$。

每次查询中，你提供三个互不相同的整数 $a, b, c$（满足 $1 \leq a,b,c \leq n$），系统将返回集合 $\{|p[a]-p[b]|,\,|p[b]-p[c]|,\,|p[a]-p[c]|\}$ 的中位数。

此处的中位数定义为：将该三元组按非递减顺序排序后所得序列中的第 $2$ 个元素（按 $1$-索引计）。例如，$\{4,6,2\}$ 的中位数是 $4$，而 $\{0,123,33\}$ 的中位数是 $33$。

你能否在不超过 $2n+420$ 次查询内找出这个秘密排列？

注意：评测程序是非自适应的，即该排列在任何查询发起前就已固定。

The first line of input contains a single integer $t$ $(1 \leq t \leq 1000)$ — the number of testcases.

The first line of each testcase consists of a single integer $n$ $(20 \leq n \leq 100000)$ — the length of the secret permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $100000$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$20 \leq n \leq 100000$）—— 表示秘密排列的长度。

保证所有测试用例的 $n$ 值之和不超过 $100000$。

The secret permutation is ${9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}$.

For the first query, the values of $(a,b,c)$ is $(1,5,2)$. Since $p[1]=9$, $p[5]=16$ and $p[2]=10$. The return value is the median of ${|9-16|,|16-10|,|9-10|}$ which is $6$.

For the second query, the values of $(a,b,c)$ is $(20,19,2)$. Since $p[20]=1$, $p[19]=13$ and $p[2]=10$. The return value is the median of ${|1-13|,|13-10|,|1-10|}$ which is $9$.

By some miracle, we have figured out that the secret permutation is ${9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}$. We output it and receive $1$ from the interactor, meaning that we have guessed the secret permutation correctly.

秘密排列为 $\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$。

对于第一次查询，$(a,b,c)$ 的值为 $(1,5,2)$。由于 $p[1]=9$，$p[5]=16$，且 $p[2]=10$，返回值为集合 $\{|9-16|,|16-10|,|9-10|\}$ 的中位数，即 $6$。

对于第二次查询，$(a,b,c)$ 的值为 $(20,19,2)$。由于 $p[20]=1$，$p[19]=13$，且 $p[2]=10$，返回值为集合 $\{|1-13|,|13-10|,|1-10|\}$ 的中位数，即 $9$。

凭借某种奇迹，我们已推断出秘密排列为 $\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$。我们将其输出，交互器返回 $1$，表示我们已正确猜中该秘密排列。