这是一个交互问题。
Imur Ishakov 决定为喜欢玩著名游戏“帽子”的人们组织一个俱乐部。该俱乐部有 n 个学生参观,其中 n 是偶数。伊穆尔将他们全部排成一圈,并举行抽签将学生分成两两,但出了问题。对参与者进行编号,以便参与者 i 和参与者 i + 1 (1 ≤ i ≤ n - 1) 以及参与者 n 和参与者 1 相邻。每个学生都得到一张带有数字的纸,其中每两个相邻学生的数字正好相差 1。计划是让具有相同数字的学生成对,但事实证明并非所有数字都恰好出现两次。
如您所知,最方便的方法是当对方坐在您对面时向他解释这些话。 Students with numbers i and $$i + \frac{n}{2}$$ sit across each other.伊穆尔想知道是否有两个人坐在一起并给出了相同的数字。帮助他找到这样的人(如果存在的话)。
您可以提出“学生 i 收到了哪个号码?”形式的问题,目标是确定所需的配对是否存在于不超过 60 个问题中。
输入
首先给出偶数 n (2 ≤ n ≤ 100 000) — 学生总数。
您最多可以提出 60 个问题。
输出
要询问有关学生 i (1 ≤ i ≤ n) 的问题,您应该打印 «?我”。然后从标准输出中,您可以读取学生 i 收到的数字 ai (- 109 ≤ ai ≤ 109)。
当您找到所需的对时,您应该打印 «! i»,其中 i 是属于该对 (1 ≤ i ≤ n) 的任何学生。如果你确定这样的对不存在,你应该输出 «! -1»。在这两种情况下,您都应该立即终止该程序。
包含您答案的查询不计入 60 个查询的限制。
请确保在每个命令后刷新标准输出。例如,在C++中使用函数fflush(stdout),在Java中调用System.out.flush(),在Pascal中使用flush(output)和Python语言的stdout.flush()。
黑客攻击
使用以下格式进行黑客攻击:
在第一行中,打印一个偶数 n (2 ≤ n ≤ 100 000) — 学生总数。
在第二行中打印 n 个整数 ai (- 109 ≤ ai ≤ 109),用空格分隔,其中 ai 是给第 i 个学生的数字。任何两个相邻元素(包括 n 和 1)必须相差 1 或 - 1。
被黑客攻击的解决方案将无法直接访问序列 ai。
示例
输入 #1
8 2 2
输出 #1
? 4 ? 8 ! 4
输入 #2
6 1 2 3 2 1 0
输出 #2
? 1 ? 2 ? 3 ? 4 ? 5 ? 6 ! -1
注意
语句中的输入输出说明了交互示例。
在第一个示例中,所选序列为 1, 2, 1, 2, 3, 4, 3, 2
在第二个示例中,选择序列为 1, 2, 3, 2, 1, 0。