本题与另外两个版本的唯一区别在于最大询问次数。在这个版本中，你最多允许进行 20 次询问。只有当本题的所有版本都被解决时，你才能进行 hack。

这是一个交互式问题。

“大家注意啦！Doremy 的完美数据结构课马上就要开始啦！如果你想拥有和我一样高的 IQ，就快来加油吧！”在今天的数据结构课上，Doremy 正在向大家介绍一种强大的数据结构——Doremy 树！现在，她给你出了一个测验，以证明你在课堂上认真听讲了。

给定一个长度为 $m$ 的数组 $a$，Doremy 树支持询问 $Q(l, r, k)$（其中 $1 \le l \le r \le m$ 且 $1 \le k \le m$），该询问返回数组 $\lfloor \frac{a_l}{k} \rfloor, \lfloor \frac{a_{l+1}}{k} \rfloor, \dots, \lfloor \frac{a_r}{k} \rfloor$ 中不同整数的个数。

Doremy 有一个由 $1$ 到 $n$ 的整数构成的隐藏排列 $p$。你可以进行询问，在每次询问中，你给出 3 个整数 $l, r, k$（$1 \le l \le r \le n, 1 \le k \le n$）并接收数组 $p$ 的 $Q(l, r, k)$ 值。你能在最多 20 次询问内找到满足 $p_y = 1$ 的下标 $y$（$1 \le y \le n$）吗？

请注意，排列 $p$ 在进行任何询问之前就已经确定。

交互

你首先需要从标准输入中读取一个整数 $n$（$3 \le n \le 1024$）—— 排列的长度。

要进行询问，你应该在单独的一行中输出：

• ? l r k（$1 \le l \le r \le n, 1 \le k \le n$）

在每次询问后，你应该读取一个整数 $x$ —— 即 $p$ 的 $Q(l, r, k)$ 值。在这个版本的题目中，你最多可以进行 20 次这样的询问。

要给出答案，你应该在单独的一行中输出：

• ! y（$1 \le y \le n$）

其中 $p_y = 1$。

在输出询问或答案后，请不要忘记输出换行符并刷新输出缓冲区（flush）。否则，你将获得 Idleness limit exceeded。为此，你可以使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• 其他语言请参阅相应文档。

Hack 格式

Hack 文件的第一行包含一个整数 $n$（$3 \le n \le 1024$）—— 排列的长度。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 该排列。

样例

输入样例 1

5

2

2

1

3

输出样例 1

? 1 3 4

? 3 5 3

? 3 4 5

? 3 5 2

! 4

说明

样例中的排列为 $[3, 5, 2, 1, 4]$。

样例中的输入和输出展示了在该测试点上可能进行的一种交互过程（插入空行仅为了清晰起见）。

在该交互过程中：

• 对于第一次询问，$\lfloor \frac{3}{4} \rfloor = 0, \lfloor \frac{5}{4} \rfloor = 1, \lfloor \frac{2}{4} \rfloor = 0$，因此不同整数的个数（答案）为 2。
• 对于第二次询问，$\lfloor \frac{2}{3} \rfloor = 0, \lfloor \frac{1}{3} \rfloor = 0, \lfloor \frac{4}{3} \rfloor = 1$，因此答案仍为 2。
• 对于第三次询问，$\lfloor \frac{2}{5} \rfloor = 0, \lfloor \frac{1}{5} \rfloor = 0$，因此答案为 1。
• 对于第四次询问，$\lfloor \frac{2}{2} \rfloor = 1, \lfloor \frac{1}{2} \rfloor = 0, \lfloor \frac{4}{2} \rfloor = 2$，因此答案为 3。

在 4 次询问后得到了正确答案，因此该过程将被判定为正确。