Problem O: Binary Search - Lower Bound

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $471$ 正确数量 $385$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL 二分查找

Lower Bound 

For a given sequence A={a0,a1,...,an−1} which is sorted by ascending order, find the lower bound for a specific value k given as a query. 

lower bound: the place pointing to the first element greater than or equal to a specific value, or n if there is no such element.

The input is given in the following format.

 n 

a0 a1,...,an−1 

k1 

k2 

kq 

The number of elements n and each element ai are given in the first line and the second line respectively. 

In the third line, the number of queries q is given and the following q lines, q integers ki are given as queries.


For each query, print the position i (i=0,1,...,n) of the lower bound in a line.
4
1 2 2 4
3
2
3
5
1
3
4

1≤n≤100,000 

1≤q≤200,000 

0≤a0≤a1≤...≤an−1≤1,000,000,000 

0≤ki≤1,000,000,000