查找第一个不小于

课程自编 · 整数二分边界

题目描述

给出一个长度为 $n$ 的非递减整数序列 $a_1,a_2,\dots,a_n$，回答 $q$ 次询问。每次询问给出整数 $x$，求最小的下标 $i$，使得 $a_i \ge x$；若不存在，输出 $n+1$。下标从 $1$ 开始。

输入格式

第一行两个整数 $n,q$。第二行 $n$ 个整数，保证非递减。接下来 $q$ 行，每行一个整数 $x$。

输出格式

对每个询问输出一行，表示第一个不小于 $x$ 的位置；不存在则输出 $n+1$。

数据范围与约定

$1 \le n,q \le 2\times 10^5$，$-10^9 \le a_i,x \le 10^9$，且 $a_1 \le a_2 \le \cdots \le a_n$。

样例输入

5 3
1 3 5 7 9
4
1
10

样例输出

3
1
6

样例说明

$4$ 的第一个不小于它的数是 $5$，位置为 $3$；$1$ 对应位置 $1$；$10$ 大于所有数，输出 $n+1=6$。

说明

课程自编题，数据由 src/gen.py 生成。