CF1019B.The hat

This is an interactive problem.

Imur Ishakov decided to organize a club for people who love to play the famous game «The hat». The club was visited by n students, where n is even. Imur arranged them all in a circle and held a draw to break the students in pairs, but something went wrong. The participants are numbered so that participant i and participant i + 1 (1 ≤ i ≤ n - 1) are adjacent, as well as participant n and participant 1. Each student was given a piece of paper with a number in such a way, that for every two adjacent students, these numbers differ exactly by one. The plan was to form students with the same numbers in a pair, but it turned out that not all numbers appeared exactly twice.

As you know, the most convenient is to explain the words to the partner when he is sitting exactly across you. Students with numbers i and sit across each other. Imur is wondering if there are two people sitting across each other with the same numbers given. Help him to find such pair of people if it exists.

You can ask questions of form «which number was received by student i?», and the goal is to determine whether the desired pair exists in no more than 60 questions.

这是一个交互式问题。

伊穆尔·伊沙科夫决定为喜爱著名游戏《帽子》的人们成立一个俱乐部。共有 $ n $ 名学生来到该俱乐部，其中 $ n $ 为偶数。伊穆尔将他们全部安排成一个圆圈，并通过抽签将学生两两配对，但出了点差错。学生的编号方式为：学生 $ i $ 与学生 $ i+1 $（$ 1 \leq i \leq n-1 $）相邻，且学生 $ n $ 与学生 $ 1 $ 相邻。每位学生都获得了一张写有数字的纸条，使得任意两名相邻学生所持数字之差的绝对值恰好为 $ 1 $。原计划是将持有相同数字的学生配成一对，但结果发现并非所有数字都恰好出现两次。

众所周知，当搭档正坐在自己正对面时，向其解释词语最为方便。持有数字 $ i $ 的学生与持有数字 的学生彼此正对而坐。伊穆尔想知道：是否存在一对正对而坐的学生，他们所持数字相同？若存在，请你帮伊穆尔找出这样的一对学生。

你可以提出形如「学生 $ i $ 得到的数字是多少？」的问题，目标是在不超过 60 次提问的前提下，确定是否存在满足条件的这样一对学生。

At the beginning the even integer n (2 ≤ n ≤ 100 000) is given — the total number of students.

You are allowed to ask no more than 60 questions.

最开始给出一个偶数 $n$（$2 \leq n \leq 100\,000$）—— 学生总人数。

你最多可以提出 60 个问题。

To ask the question about the student i (1 ≤ i ≤ n), you should print «? i». Then from standard output you can read the number a__i received by student i ( - 109 ≤ a__i ≤ 109).

When you find the desired pair, you should print «! i», where i is any student who belongs to the pair (1 ≤ i ≤ n). If you determined that such pair doesn't exist, you should output «! -1». In both cases you should immediately terminate the program.

The query that contains your answer is not counted towards the limit of 60 queries.

Please make sure to flush the standard output after each command. For example, in C++ use function fflush(stdout), in Java call System.out.flush(), in Pascal use flush(output) and stdout.flush() for Python language.

Hacking

Use the following format for hacking:

In the first line, print one even integer n (2 ≤ n ≤ 100 000) — the total number of students.

In the second line print n integers a__i ( - 109 ≤ a__i ≤ 109) separated by spaces, where a__i is the number to give to i-th student. Any two adjacent elements, including n and 1, must differ by 1 or  - 1.

The hacked solution will not have direct access to the sequence a__i.

要向第 $i$ 位学生（$1 \le i \le n$）提问，你需要输出 «? $i$»。随后可从标准输出读取第 $i$ 位学生收到的数 $a_i$（$-10^9 \le a_i \le 10^9$）。

当你找到所求的配对时，应输出 «! $i$»，其中 $i$ 是该配对中任意一名学生（$1 \le i \le n$）。若你判定这样的配对不存在，则应输出 «! -1»。在这两种情况下，你都必须立即终止程序。

包含你最终答案的查询不计入最多 60 次查询的限制。

请确保每次输出命令后刷新标准输出。例如，在 C++ 中使用 fflush(stdout)，在 Java 中调用 System.out.flush()，在 Pascal 中使用 flush(output)，在 Python 中使用 stdout.flush()。

Hack 数据构造说明

请按如下格式构造 Hack 数据：

第一行输入一个偶数 $n$（$2 \le n \le 100\,000$），表示学生的总人数。

第二行输入 $n$ 个整数 $a_i$（$-10^9 \le a_i \le 10^9$），以空格分隔，其中 $a_i$ 表示需提供给第 $i$ 位学生的数值。任意两个相邻元素（包括第 $n$ 个与第 $1$ 个）的差值必须为 $1$ 或 $-1$。

被 Hack 的程序将无法直接访问序列 $a_i$。

Input-output in statements illustrates example interaction.

In the first sample the selected sequence is 1, 2, 1, 2, 3, 4, 3, 2

In the second sample the selection sequence is 1, 2, 3, 2, 1, 0.

语句中的输入-输出展示了示例交互。

第一个样例中，所选序列为 $1,\,2,\,1,\,2,\,3,\,4,\,3,\,2$。

第二个样例中，所选序列为 $1,\,2,\,3,\,2,\,1,\,0$。