EOJ Monthly 2021.3 Sponsored by TuSimple

A. 读不懂古神语的程序员不是一个合格的探险家

单点时限: 1.0 sec

内存限制: 256 MB

这是一道交互题。

QQ 小方和 QQ 小芳来到蟹老板梦幻庄园后的神秘山洞探险,想要找到传说中埋藏千年的神秘宝藏。

神秘山洞的大门上镶着 $1048576$ 块鸽子蛋大的宝石,围成了一个巨大的圆环。圆环的正中密密麻麻地刻着一些蝇头小字:

ć̮̗͎̹̼̌́́́̅́̌́́́̽́ͧ́ͨ́́̋́í̷̷̙̤͇̙ͣ́́́́́́́̂́́́̀́́̓́́̄́́̕͘͡ŕ͐́ͦ́s ̢̞͓̗̞́́̌́̅́́́́́҈̷̻́́́̔́҈̬͙̤́̍́́̄́ͩ́́̋́̀́́ͨ́ć̵̭͎̼́̾́́ͣ́̽́́̔́́́͠ ̡̡̖̻̬͉͙̥̙̞͍̞̺̔́̂́́́ͮ́́́̅́́͊́́̉́̃́͆́́͆́́ͭ́́̊́́̅́́́́͊́̀́̐́̉́ļ̸̵̷̧̡̦̠̤͎̣̖̪̯͖̱̞̱̥̦̻͍͕́́́́́́̑́́́́̈́́́̔́̈́́́́́͊́́́́́́͋́̎́͗́́͑́̄́́͐́͌́́͑́́̋́́́́́é̴̴̸̷̵̛͙̰̖̳̫̗͕̯̠͚̦̬͓̖͎̝͕̪̤ͣ́͋́́́́͛́́́́̅́́́́́́ͤ́́́̊́́́́͋́́͂́̔́́́ͥ́́̂́́̍́́́ͤ́ͮ́́́̋́̊́́̓́́́͗́́́̋́ͩ́́͂́́͢͞ͅ ̩̪́́̈́́́͟ ̸̨̨̧̛̱́͆́ͪ́̊́̆́́́ͯ́ͭ́́͗́̏́́́́ć͇̝̬́́́ŕ̷̹̪͍͎̮̳̞̠̩̺͖̎́̽́̄́̌́́ͮ́́́ͯ́́́ͬ́̑́́ͮ́͗́ͭ́́̈́́̑́́̀́̃́͊́́́̄́́́́́́́́́͘͡ͅį̞̰̤̦́́̎́́́́́̑́́́̕͠ ̷̸͖̤͎́́́́͐́́́́́́́͋́ͪ́̓́̌́͡͡ͅǵ̷̷͋́̍́͐́͆́́́͛́ḱ̡̛͔̮̜͔̳̭̝̞͍̜̲̖͌́́́́́͂́́͗́̍́́̄́̓́͌́́́̍́́̈́́́́́́́́́ͪ́́̋́̅́̌́́͘͡ͅé̸̢͓́́́̂́͑́͊́́͊́͝ ͕̣̹́̎́̆́ͫ́̉́́͂́ͭ́̈́́́ͬ́̎́̂́ͅŕ́ͅ͏̯́̀́́҉͖́́͏̶̭̠́́̉́̃́̃́́́̀́͑́́ͫ͡ ̢̧͉͖̯͕̦̗̺̭̬́́ͥ́ͪ́́́ͩ́́́́͛́̈́́̾́́ͫ́͋́̿́́̓́́̋́́́̒́̚ ̷̪̭͎́͊́́́̅́́ ̧̦̥̯̙̫͔̙͔͔́̏́́́́̑́́́́́́́́̐́́́͛́̏́̓́͊́̾́́́́̈́́́ͪ́́͐́̚̚͢ͅͅ͏́ṕ̹́́̈́ͅ͏̛͈̹͉́́̇́́́́́͝҈̵̭̟̼͖̰̖́́́́̿́́́ͭ́ͦ́ͪ́̃́́́́̽́́́͛́ͩ́́ͧ́͒́͆́͟͠͠ ̡̛͙̭̯́́́́̍́́́́̾́̉́́́ͤ́̐́́̏́̚͠͡͡į̸̷̶̧̢̡̛͎͖̫̱͙̼͕̲͍̻̞̯̖̯͍́́́́́́͗́̏́̋́̿́́́ͮ́́̉́͂́́́́̈́́̎́ͧ́́͋́́̓́́́́́͑́́́́́́́ͭ́ͩ́́̇́́́͘͡ń͓͍ͨ́́̍́́ͤ́́̆́̚ņ̸̞̥́̊́́́́ͮ́́̊́̉́́͘͏́ģ̡̛̛̼͈͇́́͋́̐́́́́̇́́͊́́́͏́̑́ǵ̺̖́́ ̴̴̨̡͎̖͈̱͙̺̱̝̥̫́́́̍́́́́́́́̉́́̄́͛́́́́́́ͭ́́ͮ́́́̓́́́͗́́́͗́́ͦ̕͞͝͞ͅ ̞̟́͒́́̀́̐́́̌́҉͕́ͬ́́ ́̽́ͭ́ḿ̵̵̛̝͓̹́͆́́̂́͊́́ͨ́́́́̔́͂́̑́̉́́́̐́͌͜͟ ́̀́ͨ́á̷̶̸̹̼͙͖͎̝̬͙̦̦̱̰́́̒́̀́͑́́́́̇́͑́ͭ́́ͧ́ͩ́́́́ͣ́́́́́̓́́̽́́́͞ ̑́҉̶̢̛͓̬̣̠͕̮̗̲͕́́̅́́͑́́́́́́̉́̎́́́̀́́́̉́́́́́̎́ͨ́ͅḿ̸̡̳̄́̏́͂́́́̆́ ̥́͒́́̄́̀́҈̫̮̠̤̮͓́́́́̑́́́́̀́҈͖̮̯̣͓͇́ͥ́́ͣ́̃́ͤ́ͥ́́́͐́͆́́́́̊́͗́́́́̚ ̪́x̴̸̸̴̧͙̪̱̰͈̥̗͈͎́̇́͋́́́ͤ́́́́́́̆́́́̍́ͧ́̑́́̌́́́̇́́̂́ͯ́́́́̍́́ͤ́́ͯ́́́͊́̆́́͘͢͞͡͠ḭ̢́̀́́̒́́͋́́͡ḿ̷̜̭̠̳̮́́́ͨ́ͧ́́́́̿́̋́́̀́́́̚͜͢ú̶̸̧͈̦̱̤̘̖̤̳̭̓́́́͑́ͭ́́́́ͨ́́́́́̋́̈́́́́́́́̍́ͬ́́́̌́̉́͘̕҈̢̳̣́ͨ́́́̿́́́́ͬ́҈̷̨͍̱͎̮́́ͨ́́́͂́̐́́̃́́́̈́ͣ́́͠ḿ̬͈̖́́ͪ́̈́̒́̐́́á̵̺͓̱͓̩̙̾́́́́̀́̓́́́́́̏́́́́͘̕͡ḷ̵̶̙̺͎͚͇͎́́̋́́́̍́́ͧ́̍́́́́̋́̃́͛́ͮ́́̿́́́́́͜͠͝҈̴̧̧̦̲̖̣̗͇̫̳̟͉͉̰͓́́͑́́́̃́́́́́̅́́̔́́͋́́́̈́́́́́́́́́ͣ́͢͢͢ ́́͞҈̡͉͙̟͎̝͔̳͙͖̪͇̙́́̑́͐́́́́́́́ͧ́́̃́́ͣ́́ͩ́́́͌́́̆́́̈́́͡҉̨̢̨͍̝̭̳̠́́̾́́́́́́ͩ́ͣ́́̓́́͌́ͨ́ ̖͋́̆́̓́̓́̌́́ĺͮ́̊́̓́҉́́͑́͡ó̴̧̭͔͍̜̖͉́́́̓́ͫ́́͌́̎́́́́̽́ͥ́́͂́̐́́́́̈́̊́͐́̌́́͟͝ǵ͓̰̑́̌́́̏́̌́́̏́̉́͏̵͇͖̙̝͎̝̝͎́́́́́́͋́́͌́́̏́́́ͣ́ͫ́́̊́͢ǵ͖ ̴̶̡̺̞̻̲̙͙̘͍̬́́̔́́̌́́͊́̂́́̓́̽́́̉́́́ͥ́́́̀́́́̄́́̔́́́̎́̉́͗́ͣ́́̚͟͞͝ ̡̦́́̄́̿́́é̡̪͇͍̪̹̺͔͔̙̟̲̦̤͎̭́́́́́́͆́́́́́́́́ͧ́́́́̀́́̓́͗́́́́́͟͢͠ ͉̠̭̹̥́́ͦ́́́ͥ́́́͘͏̶͎͇́̽́̆́́́́ŕ̸̻̾́ͮ́́́̄́̆́̉́͂́͏̶͓́́͋́́́̐́͢҉̮́́ ͚̰̲̟̯̫̳̹̺́́ͦ́́̂́́͛́̈́́́̔́́́́́̋́́̓́̓́͘ͅ͏̨̬̮̳́́́́́́̐́́͢͡á̑́̉́̈́́́ ̭́ͨ́́͏́̔́͂́t͓̥̯̠́͛́́́́́͆́ͦ́̄́́̍́́́͟͏̴̨̢̧͈̘͓̭̬̖̼̩̞́́͆́̊́̋́́́͗́́̓́́́́́́ͪ́̐́́́̍́́͆́́̅́́́́ͨ́̾́́́́́̚͞͡ͅͅí̀́͛́͛́ͫ́͑́́ͅŕ͉́́́̕͢҉̸̷̶̶̵̛͇͙̱̤͖̤̠́́̎́́̈́́̍́́ͫ́́́́ͭ́́́́͆́́̃́́̓́́́̅́́͗́́̄́͟͟҉̪́̔́̄́́̍́̾́̿ ̣̲̹̩́́̌́́́ͩ́́h̴̙̲̘̹́́́́́̇́́ͤ́̽́́́́́́̎́̀́͘͢͞ḿ̵̑́́́́ͭ́̚ͅ҈̷̸̢̨̛̗͖̤̼̱̝̜͕̦͚̱̣̻͖͉̳̠̙́̓́́̽́́́̾́́ͫ́́̑́́ͩ́́̑́ͭ́́́́̌́́ͥ́̊́́́́́́͊́́́̄́́̓́̎́͋́́́́́ͧ

QQ 小芳马上就认出了这些奇异文字的含义:

“这里有 $2^{20}$ 个按钮,但是你只能按 $42$ 次。

“你得要小心,一失足可成千古恨。

“从$1$ 到 $1048576$,一共 $2^{20}$ 个数字

“打乱了藏在按钮的背后,按下按钮即可显现

“但也不要紧张,你其实并不需要运势的眷顾

“最小的数和最大的数之间,无论顺还是逆着

“都已经排好了顺序。”

可是 QQ 小方还是没搞懂这段话的意思,于是 QQ 小芳贴心地翻译成了 QQ 小方喜欢的表达:

山洞大门上有一个由正整数围成的环,$1,2,\dots,2^n$ 这一共 $2^n$ 个数字打乱了摆在环上,分别藏在一颗宝石的背后。最小的数(也就是 $1$)和最大的数(也就是 $2^n$)之间的数字确保单调上升。换言之,如果你从最小的数开始顺时针读取环上的数字,直到最大的那个数,你得到的数列是单调增的;用相同的方法逆时针读取也满足这个性质。

你可以进行不超过 $2n+2$ 次查询,每次你可以指定一颗宝石,按下这颗宝石,得知这个位置上的数是什么。最后,你需要确定最大的数藏在哪里。

为了方便确定每个宝石的位置,我们从某一个位置开始从 $1$ 开始顺时针依次编号。

交互流程

在进行交互之前,你需要读入一个正整数 $n$($1 \le n \le 20$),表示环上共有 $2^n$ 个正整数。

接下来,你可以进行不多于 $2n+2$ 次询问。对于每次询问,请输出 ? x($1 \le x \le 2^n$),表示你想要知道环上 $x$ 位置上的数字。接下来,你可以从标准输入中读入对应的答案。

最后,请你输出 ! x,表示你认为最大数就在 $x$ 位置上。输出之后,请你立即结束程序。

请注意,你需要在每输出一行之后执行 flush 操作,否则你提交的程序有可能会被判定为 Idleness limit exceeded。适用于各种语言的 flush 函数如下:

  • 对于 C++ 语言,你可以使用 fflush(stdout)
  • 对于 Java 语言,你可以使用 System.out.flush()
  • 对于 Pascal 语言,你可以使用 flush(output)
  • 对于 Python 语言,你可以使用 sys.stdout.flush()

样例

Input
5

4

32
Output

? 3

? 5

! 5