Problem5650--Closest to the Left

5650: Closest to the Left

[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 maximum index of an array element not greater 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 maximum index of an array element not greater than the given one. If there are none, print $0$.

Sample 1 Input

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

Sample 1 Output

0
2
4
0
5

Source/Category

基础算法 4.15.二分