题目描述

这是一道交互题。

在校学生计算机编程俱乐部年终师生交流会上，克露丝卡尔酱参与了“砸金蛋”游戏。游戏规则如下：主持人拿出 $n$ 枚金蛋排成一排，每枚金蛋内有一张纸条，纸条上写有一个整数。金蛋内的数字满足以下条件：

• 相邻两枚金蛋内的数字之差恰好为 1
• 至少有一枚金蛋内的数字为 0

例如：$1,2,3,2,3,2,1,0,1,2,1,0$ 即为一个合法的金蛋数字序列。

游戏开始后，克露丝卡尔酱可以砸开任意一个金蛋并查看其内的数字，如果数字是 0，则游戏结束，否则游戏继续，直到砸出的数字是 0 为止。

你能帮克露丝卡尔酱设计一个策略，帮助她找到一个数字为 0 的金蛋且砸开的金蛋数量尽可能少吗？

交互方式

首先从标准输入中读入一行，仅包含一个整数 $n$ ($1\le n\le 10^4$)，表示金蛋的数量。

每次砸金蛋需要向标准输出输出一行并清空缓冲区，仅包含一个 $1\sim n$ 之间的正整数 $p$，表示需要砸开的金蛋编号。已经砸开的金蛋不能再砸。然后从标准输入中读入一行，仅包含一个整数，表示第 $p$ 个金蛋中的数字。若金蛋内的数字为 0 ，你的程序应输出一行，仅包含一个字符“!”（不包括引号），随后立即退出。

要求砸开金蛋的数量不超过最优确定性策略在所有长度为 $n$ 的金蛋数字序列上运行的最坏情况 $f(n)$。换而言之，对于任意的确定性策略，必然存在一个长度为 $n$ 的金蛋数字序列，使得该策略至少需要砸开 $f(n)$ 个蛋才能找到一个数字 0。

任何不符合交互要求的输出，包括交互格式错误、超出交互次数限制等，都会导致未定义的运行结果。

样例 #1

样例输入 #1

12

1

2

2

0

样例输出 #1

1

2

10

12

!

提示

样例展示了一个可能的交互过程，金蛋数字序列为 $1,2,3,2,3,2,1,0,1,2,1,0$，一共砸开了4个蛋，可证明 $f(12)\ge 4$，满足要求。

如何清空缓冲区：

• 在 C 和 C++ 中，使用 $\text{fflush(stdout)}$（如果你使用 $\text{printf}$）或 $\text{cout.flush()}$（如果你使用 $\text{cout}$）。
• 在 Python 中，使用 $\text{stdout.flush()}$。
• 特别地，在 C++ 中，使用 $\text{cout<<endl}$ 会自动清空缓冲区。