Upper bound
Given an array of sorted
n integers, you are asked to answer q queries. Each query is of the form “What is the first number larger than x in the given list?”.Input
The first line of the input contains two integers
n (2 ≤ n ≤ ) and q (1 ≤ q ≤ ).The next line contains
n space-separated integers ( ≤ ≤ ) in an increasing order.The final line contains
q space-separated queries ( ≤ < ).Output
The program should print
q lines. Each line should contain the answer for the corresponding query.Examples
Input | Output |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Hint
In the classical implementation of the binary search, we consider the range
[l; r) where l is inclusive and r is not. In some cases, you might want to have (l; r] instead - exclude l and include r. This will require some changes in calculating the l, r, and mid points.Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB