时间限制： 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;
}

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

子任务

对于所有数据，保证 $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$。

我们给出一组样例，你可以进行本地调试。

5
1 3 5 7 9
3
2
5
8

2
3
5

提示

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

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