The hat

题意翻译

## 背景 这是一道交互题。 一共有 $n$ 个人做成一圈,他们的编号从 $1$ 到 $n$。 现在每个人的手里面都有一个数字 $a_i$ ,并且保证每个人与他周围两个人的数字差为 $1$ ,即 $\mid a_i-a_{i\pm 1}\mid =1$ ,特别地,编号为 $1$ 与 $n$ 的人也满足这个规则。 在这个圈里面,编号为 $i$ 的人的对面坐着的是编号为 $i+\frac{n}{2}$ 的人(其中 $i\le \frac{n}{2}$),现在要你找到哪个人与他对面坐着的那个人手中的数字一样。 ## 程序输出 在最开始,交互程序会给你一个 $n(2\mid n, n\le 10^5)$ ,表示这个圈里面的人数,然后你可以输出以下两种格式的操作: 1. `? x` 表示你想询问位置为 $x$ 的人手中的数字,询问不可执行超过 $60$ 次; 2. `! x` 表示你的程序的答案,即满足 $a_x=a_{x+\frac{n}{2}}(x\le \frac{n}{2})$ ,特别地,如果找不到答案,则输出 `! -1` ; ## 交互程序输入 对于操作 $1$ ,交互程序会输出一个整数 $a_x$ 表示 $x$ 编号的人手中的数字。 对于操作 $2$ ,如果你的答案是错误的,程序会直接退出,且测试结果为 `Wrong Answer` ,否则**若无其他问题**则测试结果为 `Accepted` 。

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1019B/59f224a8151ecadc368b840c31ed2d1a88e25415.png) 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.

输入输出格式

输入格式


At the beginning the even integer $ n $ ( $ 2<=n<=100000 $ ) is given — the total number of students. You are allowed to ask no more than $ 60 $ questions.

输出格式


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 $ ( $ -10^{9}<=a_{i}<=10^{9} $ ). 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<=100000 $ ) — the total number of students. In the second line print $ n $ integers $ a_{i} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ) 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} $ .

输入输出样例

输入样例 #1

8

2

2

输出样例 #1


? 4

? 8

! 4

输入样例 #2

6

1

2

3 

2

1

0

输出样例 #2


? 1

? 2

? 3

? 4

? 5

? 6

! -1

说明

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 $ .