题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day1 T1. Точки на прямій

这是一个交互题。

在一条数轴上有 $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_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)$，表示点的数量。

输出格式

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

作为查询的响应，评测程序将返回一个整数 $f$ $(f \in \{0, 1\})$。如果 $f = 1$，则点 $x_k$ 位于点 $x_i$ 和 $x_j$ 之间；如果 $f = 0$，则点 $x_k$ 不位于它们之间。

如果查询无效（即超过最大查询次数或查询参数无效），评测程序将输出 -1 并终止运行。在这种情况下，请结束程序以获得「答案错误」的评测结果。

当你准备好给出答案时，输出 $\texttt{!}\ i\ j$ $(1 \leq i, j \leq n)$，其中 $i$ 和 $j$ 是所求的点编号。然后结束程序。

flush 操作的执行方式如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 sys.stdout.flush()。

4

1

1

? 1 4 2

? 1 4 3

! 1 4

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

数据范围与提示

详细子任务附加限制及分值如下表所示：