单点时限: 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 函数如下：
fflush(stdout)；System.out.flush()；flush(output)；sys.stdout.flush()。5 4 32
? 3 ? 5 ! 5