因为正式赛有一道交互题，所以在这儿，先让大家熟悉一下交互题的做题方式。

任务

你需要编写一个函数 find_pos，来找到一个隐藏的单调不降的有序数组中，小于等于某一个数字的数有多少个。

• find_pos(n, x)
  • n: 有序数组的长度。
  • x: 你的目标是计算小于等于 x 的数的个数。

你可以调用函数 query 以帮助你确定答案。我们会根据你调用这个函数的次数评分。

• query(i) 接受一个 $[1,n]$ 中的整数，并返回有序数组中第 $i$ 个数的值。

在一组测试数据中，find_pos 只会被调用一次。

实现细节

本题只支持 C++。

你只能提交一个源文件实现如上所述的 find_pos 函数，并且遵循下面的命名和接口。

C/C++

你需要包含头文件 find.h。

int find_pos(int n, int x);

你需要把答案以返回值的形式返回。

函数 query 的接口信息如下。

int query(int i);

注意 $i$ 的值必须在 $[1,n]$ 中。该函数的返回值是有序数组中第 $i$ 个数，即第 $i$ 小的数。

如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

评测方式

评测系统将读入如下格式的输入数据：

1. 第 $1$ 行: $n,x$，表示有序数组长度以及询问的数字 $x$。
2. 第 $2$ 行: $n$ 个空格隔开的整数，表示输入的有序数组。

在 find_pos 返回后，评测系统将输出你的答案以及 query 的调用次数。

样例输入

样例一

input

5 3
1 2 3 3 4

output

4 5

explanation

样例输出的含义为 find_pos 在 $5$ 次询问之后，返回了答案 $4$。

限制与约定

find_pos 只能进行不超过 $20$ 次询问。如果超过了这个询问数量，你的程序将无法得分，

输入保证有序数组中的所有元素以及 $x$ 都是 $[1,{10}^9]$ 中的整数。

Small Task: $n\le 20$

Large Task: $n\le {10}^5$

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例交互库下载