Mirko 拥有一个隐藏的排列 $p_1, p_2, \dots, p_N$，其中包含 $1$ 到 $N$ 的数字。他的朋友 Slavko 想要揭开 Mirko 排列的秘密，但 Mirko 只会回答特定形式的问题。
Slavko 可以选择排列的任意子序列，即一个区间 $p_i, p_{i+1}, \dots, p_j$ ($1 \le i < j \le N$)，并询问 Mirko 该区间内第二大的数字位于哪个位置。Mirko 会立即回答所求的位置。
在回答完所有问题后，Mirko 决定考验 Slavko 的知识。他会提出 $Q$ 个相同形式的询问，并要求 Slavko 对每一个询问给出正确答案。
Slavko 事先不知道 Mirko 的问题，为了不惹恼他，Slavko 希望尽可能少地提问。准确地说，Slavko 最多可以向 Mirko 提问 $K$ 次。请帮助 Slavko 提出问题，并回答 Mirko 的询问。
交互
这是一个交互式题目。你的程序需要与主办方提供的程序进行对话。
首先，你的程序需要从标准输入读取整数 $N$，即排列的长度。
接着，你可以通过向标准输出打印来发送询问。每个询问必须打印在单独的一行，格式为 ? i j，其中 $i$ 和 $j$ 是满足 $1 \le i < j \le N$ 的整数。数字 $i$ 和 $j$ 代表 Slavko 想要查询的区间边界。你的程序最多可以进行 $K$ 次此类询问。
在每次打印询问后，程序必须刷新输出（flush），并从标准输入读取询问的回答——即满足 $i \le k \le j$ 的位置 $k$。
在完成自己的提问后，程序应打印字符 ! 以表示 Slavko 的提问结束，并刷新输出。
之后，需要读取自然数 $Q$——Mirko 的询问次数。接着读取 $Q$ 个询问，每个询问格式为 a b，其中 $a$ 和 $b$ 是满足 $1 \le a < b \le N$ 的整数。在读取所有 $Q$ 个询问后，对于每一个询问，需要输出自然数 $k$——即子区间 $p_a, \dots, p_b$ 中第二大元素的位置。
在输出所有询问的答案后，你的程序需要刷新输出。在回答完最后一个询问后，程序可以结束运行。
数据范围
在所有子任务中，$N \le 512$，$K = 2048$，$Q = 2048$。
| 子任务 | 分值 | 约束 |
|---|---|---|
| 1 | 6 | $N \le 64$ |
| 2 | 10 | 不存在 $i$ 使得 $p_i > \max\{p_{i-1}, p_{i+1}\}$ |
| 3 | 11 | $p_1 = N$ |
| 4 | 13 | 不存在 $i$ 使得 $p_i < \min\{p_{i-1}, p_{i+1}\}$ |
| 5 | 26 | $N \le 256$ |
| 6 | 34 | 无额外约束 |
样例
输入格式 1
4 2 1 2 1 4 2 3
输出格式 1
? 1 2 ? 1 3 ! 4 2
说明
假设 Mirko 的排列为 $2, 1, 4, 3$。程序首先读取 $N=4$，随后进行两次询问。在输出 ! 后，读取 $Q=2$ 个询问，并依次输出答案。