该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

今天可爱的哨兵想要锻炼自己的ai系统，所以想和你玩猜数字游戏。规则很简单，它规定一个数字范围，你需要在这个范围内猜测一个数字，原则上你可以随意猜测，它会告诉你大了还是小了，直到你猜对。然而，哨兵的耐心有限，你可不能真的就是随意乱猜，这样的话，它可要喂你吃绿色小葡萄了。

题目描述

编写一个程序，在有限的猜测次数内猜出哨兵选择的秘密数字。

格式

输入

程序首先接收一个整数 $n$，表示数字范围是 $[1, n]$。

输出

程序输出猜测的数字，然后根据哨兵的回应进行下一次猜测，直到猜对。

提示：输出语句最好采用类似如下内容，否则可能无法AC！

printf("%d\n", i);
fflush(stdout);

交互过程

程序读取整数 $n$（范围上限）

程序输出猜测的数字

程序读取哨兵的回应：

-1：猜测的数字太小

1：猜测的数字太大

0：猜对了

例子

比如范围限定10，哨兵想的是3，那么最后一种可能的程序输入输出为：

10
-1
-1
0

1
2
3

注意，在如上的例子中，程序最初只会接收到一个数字10，然后当你输出1时，程序才会再次收到-1，以此类推。

限制

$1 ≤ n ≤ 1,000,000$

最多只能猜测 $⌈log₂n⌉ + 1$ 次

时间限制：1秒

内存限制：256MiB