这是一道交互题。
数轴上有 $n$ 个点，坐标分别为 $x_1, x_2, \dots, 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 \le x_k \le x_j$ 或 $x_j \le x_k \le 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$)，表示点的数量。
交互
进行询问时，请输出 ? 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 并终止程序。在这种情况下，请立即结束程序以获得“答案错误”的判决。
当你准备好给出答案时，请以 ! i j ($1 \le i, j \le n$) 的格式输出，其中 $i$ 和 $j$ 是所求的下标。之后结束程序。
flush 操作执行方式如下：
- C++:
fflush(stdout)或cout.flush()； - Java:
System.out.flush()； - Pascal:
flush(output)； - Python:
sys.stdout.flush()。
子任务
- (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 分): 无额外限制。
样例
样例输入 1
4 1 1
样例输出 1
? 1 4 2 ? 1 4 3 ! 1 4
说明
在样例中，点的坐标为 $x = [1, 2, 3, 4]$。