题目描述

这是一个交互题。

初始时，有一个数组 $a = [1, 2, \ldots, n]$，其中 $n$ 是一个奇数正整数。评测器选取了 $\frac{n-1}{2}$ 对不相交的元素对，然后将这些元素对中的元素进行交换。例如，如果 $a=[1,2,3,4,5]$，并且交换了 $1 \leftrightarrow 4$ 和 $3 \leftrightarrow 5$ 这两对元素，那么最终数组为 $[4, 2, 5, 1, 3]$。

经过这些交换后，恰好有一个元素的位置没有发生变化。你需要找出这个没有移动位置的元素。

为此，你可以进行若干次查询。每次查询，你可以选择两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）。作为回应，你将获得子数组 $[a_l, a_{l + 1}, \dots, a_r]$ 按升序排列后的结果。

请找出那个没有移动位置的元素。

你最多可以进行 $\mathbf{15}$ 次查询。

数组 $a$ 在交互开始前就已经确定，并且在你的查询过程中不会发生变化。

注意：如果数组 $b$ 是数组 $a$ 的一个子数组，那么 $b$ 可以通过从 $a$ 的开头和结尾各删除若干（可能为零）元素得到。

输入格式

第一行包含一个整数 $n$（$3 \leq n \leq 10^4$，$n$ 为奇数）——数组 $a$ 的长度。

读入 $n$ 之后，你应当开始与评测器进行交互，评测器会根据你程序的输出内容给出相应的回答。

输出格式

每进行一次查询，输出一行 "$\texttt{?}\;l\;r$"（$1 \leq l \leq r \leq n$），不包含引号。随后，你应当读入 $r-l+1$ 个整数——即 $a_l, a_{l + 1}, \dots, a_r$ 按升序排列后的结果。每个测试用例最多允许进行 $15$ 次这样的查询。

当你准备给出最终答案时，输出一行 "$\texttt{!}\;x$"（$1 \leq x \leq n$），不包含引号——表示没有移动位置的元素。给出最终答案不计入 $15$ 次查询限制。

每次输出查询后不要忘记换行。

C++代码示例

//your code
cout << "? 1 5" << endl;
//your code

输入输出样例

5

1 2 4 5

1 3 5

3

1

? 1 4

? 3 5

! 2

? 1 1

! 1

说明/提示

• 在第一个测试用例中，隐藏数组为 $[4,2,5,1,3]$，长度为 $5$。

  $\texttt{? 1 4}$ ，选手请求了子数组 $[4,2,5,1]$，评测器返回排序后的结果 $[1,2,4,5]$。

  $\texttt{? 3 5}$ 选手请求了子数组 $[5,1,3]$，评测器返回排序后的结果 $[1,3,5]$。

  $\texttt{! 2}$ 选手判断 $a_2=2$，并输出，判定答案正确。

• 在第二个测试用例中，隐藏数组为 $[1,3,2]$，长度为 $3$。

  $\texttt{? 1 1}$ 选手请求了 $[1]$，评测器返回 $[1]$。

  $\texttt{! 1}$ 选手判断 $a_1=1$，并输出。答案正确。

注意：示例输入输出中多出的换行仅为便于阅读，实际交互中不会出现。