最初，Fran 有一个空数组 $a$。Fran 处理 $n$ 个形式为 $x$ 的询问——他向 $a$ 的末尾追加 $x$ 个元素。在每次询问后，Fran 想要确定数组 $a$ 中的最小值，一旦确定，他就会将其从数组中移除，且不改变其他元素的下标。

你的任务是通过提问来确定每次询问后数组中的最小值。

交互

这是一个交互式任务。你的目标是编写一个程序来响应这些询问。

输入以包含一个整数 $n$ 的单行开始——询问的数量 ($1 \le n \le 40$)。随后是 $n$ 个询问，每个询问以 $x_i$ 开头——添加到数组中的元素数量 ($1 \le x_i \le 2000$)。

在每次询问后，你的程序可以提出形式为 ? i j 的问题。交互器将返回 $0$（如果 $a_i < a_j$）或 $1$（如果 $a_i > a_j$）。你可以假设数组中的所有元素都是不同的。必须满足 $i \neq j$，且下标 $i$ 和 $j$ 不能对应已经移除的元素。

在确定最小值后，你必须输出 ! x，这表示 $a_x$ 是数组 $a$ 中的最小值（不包括已经移除的元素）。下标 $x$ 不能对应已经移除的元素。

你可以多次提问，在输出最小值后，下一个询问开始。

一旦你确定了最小值，交互将继续进行后续询问。在最后一个询问结束后，交互结束，你的程序将根据提问次数进行评分。

数组的总长度不会超过 $2000$。

子任务

你的程序将根据提问次数获得分数。设 $q$ 为你的程序提出的问题总数。

• 如果 $q \le 2700$，你的程序将获得 $120$ 分。
• 如果 $2700 < q \le 7000$，你的程序将获得 $75$ 分。
• 如果 $7000 < q \le 2 \cdot 10^4$，你的程序将获得 $35$ 分。
• 如果 $2 \cdot 10^4 < q \le 8 \cdot 10^4$，你的程序将获得 $15$ 分。

样例

输入 1

3
3
1
0
0
1
1
1
0

输出 1

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

说明

最终数组的形式为 $3, 2, 4, 1, 5$。

第一次询问输出 $1$，因为 $a_1 > a_2$。 第二次询问输出 $0$，因为 $a_1 < a_3$。 第三次询问输出 $0$，因为 $a_2 < a_3$。

在此之后，可以确定 $a_2$ 是当前最小的元素，因此输出 ! 2。交互继续进行后续询问。