题目描述

本题是交互题。

有一个长度为 $n$ 的秘密序列 $a$，序列中的所有元素互不相同。你不能直接看到这些元素，只能通过询问获得信息。

一次询问需要指定一个连续下标区间 $[l,r]$，且区间长度至少为 $2$。交互器会观察 $a_l,a_{l+1},\ldots,a_r$ 这些数，并返回其中第二大元素在原序列中的下标。

你的目标是在最多 $20$ 次询问内，确定整个序列中最大元素所在的下标。

输入格式

交互开始后，交互器首先输出一个整数 $n$，表示秘密序列的长度。

在本地测试中，交互器使用隐藏输入文件保存完整序列。隐藏输入格式为：

第一行一个整数 $n$。

第二行 $n$ 个整数，构成 $1$ 到 $n$ 的一个排列。值为 $n$ 的位置即为你需要找出的答案。

输出格式

若要发起一次询问，输出：

? l r

其中 $1\le l<r\le n$。输出后必须刷新缓冲区。交互器会返回区间 $[l,r]$ 内第二大元素的下标。

若已经确定最大元素的位置，输出：

! p

其中 $p$ 是整个序列最大元素的下标。最终答案不计入询问次数。输出最终答案后刷新缓冲区并结束程序。

样例

5
3
4

? 1 5
? 4 5
! 1

样例说明

样例只表示一种可能出现的交互过程。

例如隐藏序列可以是 $[5,1,4,2,3]$。此时询问 ? 1 5，区间内第二大的数为 $4$，其下标为 $3$；询问 ? 4 5，区间内第二大的数为 $2$，其下标为 $4$。根据这些信息，可以回答最大值所在下标为 $1$。

数据范围

$2\le n\le 10^5$。

隐藏序列中的元素两两不同。

询问次数不能超过 $20$。