题目描述

已知以下程序：

#include <bits/stdc++.h>
using namespace std;
// 请在此处实现 myLower_bound 函数 
// ...
int a[1000005];
int main() {
	// 关闭同步流，避免 cin 和 cout 超时 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int x;
		cin >> x;
		// 调用函数并计算出下标
		int p = myLower_bound(a + 1, a + n + 1, x) - a;
		if (p == n + 1) cout << "-1 ";
		else cout << p << " ";
	}
	return 0;
}

主函数的作用是：

• 输入 $n$ 个正整数到数组 a 中并从小到大排序。
• 再进行 $q$ 次查询，每次查询输出数组 a 中第一个大于等于 $x$ 的数字的下标。
• 如果不存在 x，则输出 -1。

你的任务是实现 myLower_bound 函数：

• 传入 a + 1、a + n + 1、x。
• 使用二分查找，查找数组 a 中 a + 1 ~ a + n 区间的数字（即 a[1] ... a[n]）里第一个大于等于 x 的数字的地址，并返回这个地址。
• 如果不存在 x，则返回 a + n + 1。

题型说明

解题时可以把题目提供的程序复制到编译器中，编写对应所需的函数，测试通过后只需要提交所需的函数，如果提交完整程序反而会 WA。

格式要求

输入格式

第一行输入一个整数 $n(1 \leq n \leq 10^6)$。

接下来一行输入 $n$ 个不超过 $10^6$ 的正整数。

紧接着再输入一个整数 $q(1 \leq q \leq 10^6)$。

接下来一行再输入 $q$ 个不超过 $10^6$ 的正整数。

输出格式

输出 $q$ 个整数，用空格隔开。

样例

3
2 4 7
10
1 2 3 4 5 6 7 8 9 10

1 1 2 2 3 3 3 -1 -1 -1