Description

Ivan 想和你玩一个游戏。他选取了从 $1$ 到 $n$ 的所有整数，打乱顺序后，将所有偶数放入数组 $e$，所有奇数放入数组 $o$。

你的任务是找出数组 $e$ 和 $o$。

你可以向 Ivan 提出特定类型的问题。每个问题包含两个整数 $i$ 和 $j$。对于每个问题，Ivan 会回答 $e[i] < o[j]$ 是否成立。

你最多可以提出 $300,000$ 个问题。

交互协议

首先，测试系统会输入整数 $n (1 \le n \le 10,000)$ —— Ivan 使用的整数数量。

你的解决方案应输出两种类型的请求：

• “? i j”。其中 $1 \le i \le ⌊n/2⌋, 1 \le j \le ⌈n/2⌉$。测试系统会响应符号 $“<”$ 表示 $e[i] < o[j]$，否则响应符号 $“>”$。

• “! $e_1\ e_2\ \cdots e_{⌊n/2⌋}\ o_1\ o_2 \cdots o_{⌈n/2⌉}$” 表示你的程序确定的 $e$ 和 $o$ 的值。

在每次请求后不要忘记刷新输出缓冲区！

你的解决方案必须恰好发出一次第二种类型的请求，且该请求必须是最后一个请求，并在发出后正常终止。

你的解决方案最多可以发出 $300,000$ 次第一种类型的请求。

每个测试用例的 $n$ 值是固定的，数字使用 Java 内置的洗牌函数（使用固定种子）进行打乱。

5
>
>
<
>
<
<

? 1 1
? 1 2
? 1 3
? 2 1
? 2 2
? 2 3
! 4 2 1 3 5

Hint

题面翻译由 Deepseek 提供。