时间限制： 1.0 秒

空间限制： 256 MB

题目描述

已知一个长度为 $n$ 的非递减正整数向量 $a_1,...,a_{n}$（注意：本题下标从 $1$ 开头），一共进行 $T$ 次操作，每次给定一个数 $x$，查找向量中 $\ge x$ 的最小位置。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 bound.h。

你需要实现一个函数 int lowerBound(int, int)，传入的第一个参数为 $x$，第二个参数为向量长度 $n$；返回值见题目描述，为向量中 $\ge x$ 的最小位置。如果 $n$ 个数都 $<x$，返回 $n+1$。

你可以调用函数 int get(int)，传入参数是一个介于 $1$ 到 $n$ 之间的整数 $x$，返回值为 $a_x$。你无法得知具体的正整数序列，只能使用 get 函数获取。当单次调用 lowerBound 时，get 调用次数超过 $30$，或者传入参数越界，则会报 Runtime Error。

你可以调用函数 int getFib(int)，传入是一个介于 $1$ 到 $30$ 的整数 $x$，返回第 $x$ 个斐波那契数 $fib(x)$（其中 $fib(1)=fib(2)=1$）。当单次调用 lowerBound 时，getFib 调用次数超过 $100$，或者传入参数越界，则会报 Runtime Error。

以下我们给出一个代码提交实例（会固定返回答案 $n+1$，仅作为示例，不保证能得分）：

#include "bound.h"
int lowerBound(int x, int n)
{
    return n + 1;
}

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

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 bound.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库先输入一个整数 $n$，接下来输入 $n$ 个数表示有序序列。接下来输入一个整数 $q$，接下来输入 $q$ 个数。对于每一次查询会输出一行一个整数表示对应的结果。

5
1 3 5 7 9
3
2
5
8

2
3
5

子任务

对于所有数据，保证 $1\le n\le 10^5,~1\le T\le 2\times 10^5,1\le a_1\le a_2\le \cdots\le a_n\le 10^8$。

提示

Chap 02 向量，有序向量查找。

可以用来练习二分查找和 Fibonacci 查找。