这是一道交互式题目。

题目描述

33DAI 隐藏了一个长度为 $N$ 的排列 $P$，也就是一个包含从 $1$ 到 $N$ 所有整数恰好一次的数组。你的任务是找出值为 $1$ 的元素所在的位置（即下标，下标从 $1\sim n$ 编号）。

为了做到这一点，你可以进行一种查询。

你可以选择两个整数 $l$ 和 $r$（$1 \le l < r \le N$），并向交互器发出查询 ? l r。

交互器会返回在数组 $P$ 的子段 $P_l \sim P_r$（也就是从第 $l$ 个元素到第 $r$ 个元素）中，值第二小的元素的下标。

例如，如果 $N=5$, $P = [3, 5, 1, 4, 2]$，你查询 ? 1 5。子段 $P_1 \sim P_5$ 是整个数组。其中最小的元素是 $1$（在下标 3），第二小的元素是 $2$（在下标 5）。所以交互器会返回 5。你可以通过输入得到交互器的返回值。

你的目标是在不超过 $40$ 次 查询内找到值为 $1$ 的元素的下标。

找到答案后，你需要输出 ! k，其中 $k$ 是值为 $1$ 的元素的下标。输出答案后，你的程序应立即终止。

交互格式

首先，你的程序需要从标准输入读取一个整数 $N$。

然后，你可以开始进行查询。 要进行一次查询，请在单行（'\n' 结尾）中输出 ? l r ($1 \le l < r \le N$)。然后你必须刷新输出缓冲区。之后，从标准输入读取一个整数，即查询的回答。

当你确定了值为 $1$ 的元素的下标 $k$ 时，输出 ! k。然后请刷新缓冲区并终止程序。

在 C++ 中，cout 可以使用 cout.flush(); 刷新，printf 可以使用 fflush(stdout); 来强制刷新缓冲区。

5
5
1
1
2

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

在这个例子中，隐藏的排列可能是 $P = [3, 5, 1, 4, 2]$。

• 首先程序读入 $N=5$。
• ? 1 5 -> 返回 5(第二小元素 $2$ 的位置)
• ? 1 4 -> $P_1 \sim P_4 = [3, 5, 1, 4]$。最小值是 $1$ (下标 3)，第二小是 $3$ (下标 1)。返回 1。
• ? 1 3 -> $P_1 \sim P_3 = [3, 5, 1]$。最小值是 $1$ (下标 3)，第二小是 $3$ (下标 1)。返回 1。
• ? 1 2 -> $P_1 \sim P_2 = [3, 5]$。最小值是 $3$ (下标 1)，第二小是 $5$ (下标 2)。返回 2。
• 通过一系列查询，程序最终确定 $1$ 在下标 3，输出 ! 3。

数据规模与约定

对于 $100\%$ 的数据，保证：$2 \le N \le 2000$。

• 子任务 1 (30 分)：$2 \le N \le 20$。
• 子任务 2 (30 分)：排列 $P$ 保证是 "V" 形的。也就是说，存在一个下标 $pos$ ($1 \le pos \le N$)，使得 $P_{pos}=1$，并且 $P_1 \sim P_{pos}$ 是严格递减的， $P_{pos} \sim P_N$ 是严格递增的。例如，如果 $N=5, pos=3$, 一个可能的 "V" 形排列是 $[4, 2, 1, 3, 5]$。
• 子任务 3 (40 分)：没有特殊限制。