题目背景

本题为“交互（函数接口式）”类型题目的测试用题。

题目描述

这是一道交互题。

你需要猜出一个 $1 \sim n$ 之间的整数 $x$。

每次你可以询问一个 $1 \sim n$ 之间的整数 $y$，然后得知 $x$ 与 $y$ 的大小关系（小于、大于、或等于）。

你需要在 $\lfloor \log_2 n \rfloor$ 次内猜出这个整数 $x$。

实现细节

请确保提交的程序开头包含 #include "guess.h"。

你不需要，也不应该实现主函数。

你需要实现以下函数：

int guess(int n);

• $n$ 即为题目描述中的 $n$。
• 该函数需要返回 $x$，即你需要猜得的整数。
• 对于每个测试点，该函数会被交互库调用恰好一次。

你可以通过调用以下函数向交互库进行一次询问：

int ask(int y);

• 需要保证 $y$ 的值在 $1 \sim n$ 之间。
• 该函数会返回 $x$ 与 $y$ 的大小关系：
  • 若 $x > y$ 则返回 $1$；
  • 若 $x = y$ 则返回 $0$；
  • 若 $x < y$ 则返回 $-1$。
• 你可以调用该函数不超过 $2 \times 10^5$ 次。

题目保证在调用 ask 函数不超过 $2 \times 10^5$ 次的条件下，交互库运行所需的时间不超过 0.1 秒；交互库使用的内存大小固定，且不超过 64 MiB。

测试程序方式

下发文件中的 grader.cpp 是提供的交互库参考实现，实际评测时所用的交互库实现与该参考实现有所不同，因此你的解法不应该依赖交互库实现。

你可以使用如下命令编译得到可执行文件：

g++ grader.cpp guess.cpp -o guess -O2 -std=c++14 -static

其中 guess.cpp 是你的源代码的文件名。

对于编译得到的可执行文件：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个正整数 $n, x$。
• 输入完成后，交互库将调用 guess 函数。guess 函数返回后，交互库会输出以下信息：
  • 输出的第一行为你猜得的 $x$ 以及实际的 $x$。
  • 输出的第二行为你进行的询问次数以及 $\lfloor \log_2 n \rfloor$ 的值。
• 如果 guess 函数未正确返回或你调用了 ask 函数超过 $2 \times 10^5$ 次，交互库将不能保证输出正确的信息。

交互示例

假设 $n = 7$，$x = 3$。

下面是一个正确的交互过程：

选手程序	交互库	说明
	调用 guess(7)	开始测试
调用 ask(4)	返回 $-1$	$x = 3 < 4 = y$
调用 ask(2)	返回 $1$	$x = 3 > 2 = y$
运行结束并返回 $3$	输出信息	交互结束，结果正确

在这个例子中，选手程序进行了 $2$ 次询问，而 $\lfloor \log_2 n \rfloor = 2$，故询问次数满足限制。

下发文件说明

下发文件 guess.zip（点击即可下载）中包含：

1. grader.cpp 是提供的交互库参考实现。
2. guess.h 是头文件，你不用关心具体内容。
3. template_guess.cpp 是提供的示例代码，你可在此代码的基础上实现。

评分方式

注意：

• 你不应当通过非法方式获取交互库的内部信息；
• 实际评测时的交互库与交互库的参考实现不同，且可能是适应性的。

评分方式如下：

• 如果 guess 函数的返回值正确，且调用了 ask 函数不超过 $\lfloor \log_2 n \rfloor$ 次，该测试点获得满分；
• 否则，该测试点获得零分。

数据范围

对于所有测试数据，$1 \le x \le n \le 10^5$。