题目描述

这是一道交互题。

数轴上有 $n$ 个整数坐标的点 $x_1, x_2, \ldots, x_n$。保证对于所有 $1\le i\le n$ 都有 $1\le x_i\le n$。

当且仅当点 $x_k$ 位于由点 $x_i$ 和 $x_j$ 构成的线段上时，我们称点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间。形式化地说，点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间当且仅当 $x_i \leq x_k \leq x_j$ 或 $x_j \leq x_k \leq x_i$。

你需要找到任意两个下标 $i$ 和 $j$，使得所有 $n$ 个点都位于点 $x_i$ 和 $x_j$ 之间。

你可以使用以下查询：选择三个下标 ($i$, $j$, $k$) 并查询点 $x_k$ 是否在点 $x_i$ 和 $x_j$ 之间。

你最多可以使用 $22222$ 次查询。

保证点的坐标在交互开始前就已固定。换句话说，交互器不是自适应的。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 2 \cdot 10^4$) —— 点的数量。

输出格式

要发起查询，请输出 "$\tt{?}$ $i$ $j$ $k$" ($1 \le i, j, k \le n$)，然后输出换行符并执行 $\tt{flush}$ 操作。

作为查询的响应，评测程序将输出一个整数 $f$ ($f \in \{0,1\}$)。如果 $f = 1$，表示点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间；如果 $f = 0$，则表示不在。

如果查询无效（即超过最大查询次数或查询参数无效），评测程序将输出 $\texttt{-1}$ 并终止。此时，程序应立即终止，否则会被判为 $\tt{Wrong Answer}$。

当你准备好给出答案时，请以 "$\tt{!}$ $i$ $j$" ($1 \leq i, j \leq n$) 的格式输出，其中 $i$ 和 $j$ 是所求点的下标。输出后终止程序。

$\tt{flush}$ 操作的具体实现方式如下：

• C++：$\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$；
• Java：$\texttt{System.out.flush()}$；
• Pascal：$\texttt{flush(output)}$；
• Python：$\texttt{sys.stdout.flush()}$。

可以参考给出的模板代码。

提示

在示例中，点的坐标为 $x = [1, 2, 3, 4]$。

评分标准

• （$17$ 分）：$n \le 20$；
• （$16$ 分）：$n \le 100$；
• （$30$ 分）：$n \le 10000$；
• （$23$ 分）：$n \le 20000$，$x_i \le 2$；
• （$10$ 分）：$n \le 12000$；
• （$4$ 分）：无额外限制。

翻译由 DeepSeek V3 完成