AT_kupc2020_j.Median Query

Alice 持有一个由整数 $1$ 到 $N$ 组成的排列 $a_1, a_2, \ldots, a_N$，她想尽量隐藏这个排列。但是，Bob 不喜欢秘密，他很想找出这个排列。为了保护她的秘密，Alice 只会告诉 Bob 这组排列的大小 $N$，并允许以下两种类型的询问。

• 类型 $1$ 询问：选择三个不同的整数 $i, j, k\ (1 \leq i, j, k \leq N)$，Alice 将告知 $a_i, a_j, a_k$ 中的中位数。
• 类型 $2$ 询问：选择两个不同的整数 $i, j\ (1 \leq i, j \leq N)$，Alice 将告知 $a_i, a_j$ 中较小的那个的索引。如果 $a_i < a_j$，返回 $i$；否则返回 $j$。

必须注意的是，Alice 不希望透漏过多信息，她对类型 $1$ 询问的回答次数限制为 $2N$ 次，对类型 $2$ 询问的回答次数限制为 $2$ 次。更具挑战性的是，Alice 可能会在不违反之前回答的情况下，随时调整排列的顺序。

Bob 非常忙碌，没有时间仔细考虑询问的策略。请你帮助 Bob，编写一个程序，通过有限的询问来确定排列的具体顺序。

输入格式

首先输入一个整数，表示排列的大小 $N$。

进行类型 $1$ 询问时，程序需按以下格式输出：

? 1 i j k

其中 $i, j, k$ 是 $1$ 到 $N$ 的不同整数。输出后需换行。

类型 $1$ 询问的答案将以下形式给出：

m

其中 $m$ 表示 $a_i, a_j, a_k$ 三个数的中位数，为 $1$ 到 $N$ 的整数。

进行类型 $2$ 询问时，程序需按以下格式输出：

? 2 i j

其中 $i, j$ 是 $1$ 到 $N$ 的不同整数。输出后需换行。

类型 $2$ 询问的答案将以下形式给出：

k

其中 $k$ 是 $i$ 或 $j$，取决于 $a_i$ 和 $a_j$ 的大小关系。当 $a_i < a_j$ 时返回 $i$，否则返回 $j$。

询问次数限制如下：类型 $1$ 的询问最多 $3N$ 次，类型 $2$ 的询问最多 $3$ 次。超过限制将导致结果为 查询次数超过限制。

在进行若干次询问后，你要猜出排列，并按以下格式输出结果：

! a_1 a_2 a_3 \cdots a_N

输出结果后，程序须立即结束。否则，结果将不可预期。

此外，输出格式的任何偏差都将导致结果不可预期。

每次输出后，务必刷新输出缓冲区。例如，在 C 语言中可用以下代码刷新：

printf("? 1 %d %d %d\n", i, j, k); fflush(stdout);

在 C++ 中可用以下代码：

cout << "? 1 " << i << " " << j << " " << k << endl;

请注意，排列最初可能并未固定。

数据范围与提示

• 约束条件：$4 \leq N \leq 6 \times 10^4$。

• 评分标准：

  • 不超过询问限额且正确输出排列得 20 分。
  • 如果类型 $1$ 询问不超过 $2N$ 次，而类型 $2$ 询问不超过 $2$ 次，并且正确输出排列，则得满分。

示例

假设排列为 "3, 5, 4, 1, 2"，可能的输入和输出如下：

输出	输入	说明
5		输入的排列大小是 5
? 1 1 2 3		发起类型 $1$ 询问，$a_1, a_2, a_3$ 的中位数
4		$a_1, a_2, a_3$ 的中位数是 $4$
? 2 2 4		发起类型 $2$ 询问，比较 $a_2$ 和 $a_4$，返回较小的下标
4		$a_2 > a_4$，返回下标 $4$
? 1 1 5 4		发起类型 $1$ 询问，$a_1, a_5, a_4$ 的中位数
2		$a_1, a_5, a_4$ 的中位数是 $2$
! 3 5 4 1 2		猜测排列为 "3, 5, 4, 1, 2"

这��输入输出仅为示例，实际测试需要适应不同情况。

本翻译由 AI 自动生成