能买到饮料的商店数

课堂重述版 · 二分查找 · 来源：Codeforces 706B Interesting drink

题目描述

有 $n$ 家商店，第 $i$ 家商店的饮料价格为 $p_i$。有 $q$ 次询问，每次给出预算 $m$，求价格不超过 $m$ 的商店数量。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $p_1,p_2,\dots,p_n$。第三行一个整数 $q$。接下来 $q$ 行，每行一个整数 $m$。

输出格式

对每个预算输出一行，表示价格不超过该预算的商店数量。

数据范围与约定

$1 \le n,q \le 10^5$，$1 \le p_i \le 10^5$，$1 \le m \le 10^9$。

样例输入

5
3 10 8 6 11
4
1
10
3
11

样例输出

0
4
1
5

样例说明

价格排序后为 $3,6,8,10,11$。预算 $10$ 能覆盖前 $4$ 家；预算 $1$ 覆盖 $0$ 家；预算 $3$ 覆盖 $1$ 家；预算 $11$ 覆盖全部 $5$ 家。

说明

课堂重述题，数据由 src/gen.py 重新生成，和原站评测数据不同。