题目描述

有 $n$ 名同学围成一圈，$n$ 为偶数。第 $i$ 名与第 $i+1$ 名相邻，且第 $n$ 名与第 $1$ 名相邻。每名同学手里有一个整数，任意相邻两人的整数之差的绝对值都恰好为 $1$。

编号相差 $\frac n2$ 的两人坐在正对面。你需要判断是否存在一对正对面同学拿到相同整数；若存在，输出其中任意一人的编号，否则输出 $-1$。

你不能直接看到这些整数，只能通过询问获得某个编号的整数。

输入格式

交互开始时，交互器会先给出偶数 $n$。

本地交互器的隐藏输入采用如下格式：第一行是 $n$，第二行是 $a_1,a_2,\ldots,a_n$。要求 $n$ 为偶数，且相邻位置（包括 $n$ 与 $1$）的值差绝对值均为 $1$。

输出格式

询问第 $i$ 个同学的整数时，输出一行 ? i，其中 $1\le i\le n$，然后刷新输出；交互器会返回 $a_i$。

如果找到正对面且数值相同的一对，输出一行 ! i，其中 $i$ 是这对中的任意一个编号。若确定不存在，输出一行 ! -1。最终回答不计入询问次数。

样例

8
2
2

? 4
? 8
! 4

6
1
2
3
2
1
0

? 1
? 2
? 3
? 4
? 5
? 6
! -1

样例说明

样例只表示交互过程。第一组隐藏序列可为 $[1,2,1,2,3,4,3,2]$，第二组隐藏序列可为 $[1,2,3,2,1,0]$。

数据范围

$2\le n\le 10^5$，$n$ 为偶数，$-10^9\le a_i\le 10^9$，相邻位置的值差绝对值为 $1$，询问次数不超过 $60$。