Problem5651--Closest to the Right

5651: Closest to the Right

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Given an array of $n$ numbers, sorted in non-decreasing order, and $k$ queries. 
For each query, print the minimum index of an array element not less than the given one.

Input

The first line of the input contains integers $n,\ k\ (0<n,\ k≤10^5)$, the length of the array and the number of queries. 
The second line contains $n$ elements of the array, sorted in non-decreasing order. 
The third line contains $k$ queries. All array elements and queries are integers, each of which does not exceed $2⋅10^9$ in absolute value.

Output

For each of the $k$ queries, print the minimum index of an array element not less than the given one. If there are none, print $n+1$.

Sample 1 Input

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

Sample 1 Output

1
3
4
1
6

Source/Category

基础算法 4.15.二分