题目描述

交互器隐藏了一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$，其中每个 $1$ 到 $n$ 的整数恰好出现一次。

若下标 $k$ 满足 $a_k<\min(a_{k-1},a_{k+1})$，则称 $k$ 是局部低点。这里规定 $a_0=a_{n+1}=+\infty$。

你需要在询问次数不超过 $100$ 的限制内，找到任意一个局部低点下标。

输入格式

交互开始时，交互器会先给出一个整数 $n$。

本地交互器的隐藏输入采用如下格式：第一行是 $n$，第二行是排列 $a_1,a_2,\ldots,a_n$。

输出格式

询问下标 $i$ 时，输出一行 ? i，其中 $1\le i\le n$，然后刷新输出；交互器会返回 $a_i$。

回答时，输出一行 ! k，其中 $k$ 必须是局部低点下标，然后刷新输出并结束程序。

样例

5
3
2
1
4
5

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

样例说明

样例是一段可能的交互记录，隐藏排列为 $[3,2,1,4,5]$。

数据范围

$1\le n\le 10^5$，隐藏数组是 $1$ 到 $n$ 的排列，询问次数不超过 $100$。