题目背景

这是一道交互题。

题目描述

珂愛给了你一个 $[1,n]$ 之间的整数 $k$，你每次可以询问一个整数 $x$，然后珂愛会告诉你 $x$ 和 $k$ 的大小关系。

你需要用尽可能少的次数猜出珂愛想的数。

你需要实现一个函数 int Chtholly(int n,int c)，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个数，返回值为你最终确定的数。

你可以调用交互库中一个叫做 Seniorious 的函数，其原型为 int Seniorious(int x)，返回值为：

• 若 $k\lt x$，则返回 $1$。
• 若 $k\gt x$，则返回 $-1$。
• 若 $k=x$，则返回 $0$。

你调用 Seniorious 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考【说明/提示】部分。

由于珂愛只会写 C++ 语言的交互库，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17）来解决本题。

输入格式

样例输入中三个数分别为 $n,c,k$。这些数据你都无法读取。

输出格式

样例输出中第一个数是你猜的 $k$，第二个数是你调用 Seniorious 函数的次数。这些数据你不必输出。

5 5 3

3 0

提示

样例解释

你要猜的 $k$ 为 $3$。

由于你和珂愛心灵相通，所以在没有调用 Seniorious 的情况下就猜出来了。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $c=n-1$。
• 对于 $100\%$ 的数据，保证 $2\leq n\leq 10^6$，$\min(20,n-1)\leq c\leq n$。

提示

关于交互题。

样例交互库源代码链接。注意，此交互库仅供测试样例使用，实际评测时的交互库此交互库不同。

如果您不知道如何在本地调试您的代码，请参考这篇文章。

请特别注意，你的答案应该作为函数的返回值给出，你不需要，也不应该向标准输出输出任何内容，否则将无法获得分数。

如果有需要，你可以在选手程序的开头加入一些头文件，当然在本题中这并不是必须的。

交互库给出的函数 Seniorious 无法直接调用，需要在选手程序中用 extern "C" 关键字声明一次。

下面给出本题的模板程序（请不要使用 gcc9 提交）：

#include <cstdio>                         // 在本题中并不是必须的

extern "C" int Seniorious(int);           // 在这里需要声明一次交互库给出的函数。

extern "C" int Chtholly(int n, int OvO) { // 在这里实现交互库要求你实现的函数。
  int ans = 1;
  for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) {
    r = (ans = mid) - 1;
  } else {
    l = mid + 1;
  }
  return ans;
}