English · Original
Chinese · Translation
Formal · Original
**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.
## Input
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.
## Output
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_.
[samples]
## Note
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.
*这是一个交互式问题。*
Imur Ishakov 决定组织一个喜爱著名游戏《帽子》的俱乐部。俱乐部共有 #cf_span[n] 名学生参加，其中 #cf_span[n] 为偶数。Imur 将他们全部围成一圈，并进行抽签以将学生配对，但出了点问题。学生编号为 #cf_span[1] 到 #cf_span[n]，使得学生 #cf_span[i] 和学生 #cf_span[i + 1]（#cf_span[1 ≤ i ≤ n - 1]）相邻，同时学生 #cf_span[n] 和学生 #cf_span[1] 也相邻。每个学生被发给一张写有数字的纸条，使得任意两个相邻学生的数字恰好相差 1。计划是将拥有相同数字的学生配对，但结果发现并非所有数字都恰好出现了两次。
众所周知，当你的搭档恰好坐在你正对面时，解释起来最方便。学生 #cf_span[i] 和学生 #cf_span[i + n/2]（对 #cf_span[1 ≤ i ≤ n/2]）正对面坐着（下标按模 #cf_span[n] 计算）。Imur 想知道是否存在两个正对面的学生拥有相同的数字。请帮他找出这样的一对学生（如果存在）。
你可以提问：“学生 #cf_span[i] 被分配了什么数字？”，目标是在不超过 #cf_span[60] 次提问内确定是否存在这样的配对。
开始时会给出一个偶数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——学生的总人数。
你最多可以提问 #cf_span[60] 次。
要询问学生 #cf_span[i]（#cf_span[1 ≤ i ≤ n]）的数字，请输出 «_? #cf_span[i]_»。然后从标准输出中读取学生 #cf_span[i] 被分配的数字 #cf_span[ai]（#cf_span[ - 109 ≤ ai ≤ 109]）。
当你找到目标配对时，应输出 «_! #cf_span[i]_»，其中 #cf_span[i] 是该配对中的任意一名学生（#cf_span[1 ≤ i ≤ n]）。如果你确定这样的配对不存在，则输出 «_! -1_»。在这两种情况下，你都应立即终止程序。
包含你答案的查询不计入 #cf_span[60] 次查询的限制。
请确保在每次命令后刷新标准输出。例如，在 C++ 中使用函数 _fflush(stdout)_，在 Java 中调用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_，在 Python 中使用 _stdout.flush()_。
*黑客模式*
用于黑客攻击的格式如下：
第一行，打印一个偶数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——学生的总人数。
第二行，打印 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[ - 109 ≤ ai ≤ 109]），以空格分隔，其中 #cf_span[ai] 是分配给第 #cf_span[i] 个学生的数字。任意两个相邻元素（包括 #cf_span[n] 和 #cf_span[1]）的差值必须为 #cf_span[1] 或 #cf_span[ - 1]。
被黑客攻击的解决方案将无法直接访问序列 #cf_span[ai]。
题面中的输入输出示例展示了交互过程。
在第一个样例中，选定的序列为 #cf_span[1, 2, 1, 2, 3, 4, 3, 2]
在第二个样例中，选定的序列为 #cf_span[1, 2, 3, 2, 1, 0]。
## Input
开始时会给出一个偶数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——学生的总人数。你最多可以提问 #cf_span[60] 次。
## Output
要询问学生 #cf_span[i]（#cf_span[1 ≤ i ≤ n]）的数字，请输出 «_? #cf_span[i]_»。然后从标准输出中读取学生 #cf_span[i] 被分配的数字 #cf_span[ai]（#cf_span[ - 109 ≤ ai ≤ 109]）。当你找到目标配对时，应输出 «_! #cf_span[i]_»，其中 #cf_span[i] 是该配对中的任意一名学生（#cf_span[1 ≤ i ≤ n]）。如果你确定这样的配对不存在，则输出 «_! -1_»。在这两种情况下，你都应立即终止程序。包含你答案的查询不计入 #cf_span[60] 次查询的限制。请确保在每次命令后刷新标准输出。例如，在 C++ 中使用函数 _fflush(stdout)_，在 Java 中调用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_，在 Python 中使用 _stdout.flush()_。
*黑客模式*
用于黑客攻击的格式如下：
第一行，打印一个偶数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——学生的总人数。
第二行，打印 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[ - 109 ≤ ai ≤ 109]），以空格分隔，其中 #cf_span[ai] 是分配给第 #cf_span[i] 个学生的数字。任意两个相邻元素（包括 #cf_span[n] 和 #cf_span[1]）的差值必须为 #cf_span[1] 或 #cf_span[ - 1]。
被黑客攻击的解决方案将无法直接访问序列 #cf_span[ai]。
[samples]
## Note
题面中的输入输出示例展示了交互过程。
在第一个样例中，选定的序列为 #cf_span[1, 2, 1, 2, 3, 4, 3, 2]
在第二个样例中，选定的序列为 #cf_span[1, 2, 3, 2, 1, 0]。
**Definitions**
Let $ n \in \mathbb{Z} $ be an even integer with $ 2 \leq n \leq 100{,}000 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers such that for all $ i \in \{1, \dots, n\} $,
$$
|a_i - a_{i+1}| = 1 \quad \text{(with } a_{n+1} = a_1\text{)}.
$$
**Constraints**
1. $ n $ is even.
2. $ |a_i - a_{i+1}| = 1 $ for all $ i \in \{1, \dots, n\} $ (cyclically).
3. The sequence $ A $ is not directly accessible; only queries of the form $ a_i $ are allowed.
4. At most 60 queries may be made.
**Objective**
Determine whether there exists an index $ i \in \{1, \dots, n\} $ such that
$$
a_i = a_{i + n/2},
$$
where indices are taken modulo $ n $ (i.e., student $ i $ is opposite student $ i + n/2 $).
If such an $ i $ exists, output `! i` for any such $ i $.
If no such pair exists, output `! -1`.
API Response (JSON)
{
"problem": {
"name": "D. The hat",
"description": {
"content": "**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 arrang",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1020D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "**This is an interactive problem.**\n\nImur 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 arrang...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "*这是一个交互式问题。*\n\nImur Ishakov 决定组织一个喜爱著名游戏《帽子》的俱乐部。俱乐部共有 #cf_span[n] 名学生参加，其中 #cf_span[n] 为偶数。Imur 将他们全部围成一圈，并进行抽签以将学生配对，但出了点问题。学生编号为 #cf_span[1] 到 #cf_span[n]，使得学生 #cf_span[i] 和学生 #cf_span[i + 1]（#cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be an even integer with $ 2 \\leq n \\leq 100{,}000 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers such that for all $ i \\in \\{1, \\dots, n\\}...",
"is_translate": false,
"language": "Formal"
}
]
}