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 语言中可用以下代码刷新：
```c
printf("? 1 %d %d %d\n", i, j, k); fflush(stdout);
```
在 C++ 中可用以下代码：
```cpp
cout
输入格式
无
输出格式
无
说明/提示
### 制約
- $ 4\ \leq\ N\ \leq\ 6\ \times\ 10^4 $
### 部分点
- タイプ $ 1 $ の質問の上限は **$ 3N $** 回、タイプ $ 2 $ の質問の上限は **$ 3 $** 回である。この上限を超えて質問をした場合は *Query Limit Exceeded* となる。
- 質問回数が上限を超えず、かつ正しい順列を出力したとき、$ 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 $" であると回答しているこれは入出力の一つの例であり、意味のある入出力をしているとは限らない。