Upper bound

Given an array of n integers, you are asked to answer q queries. Each query is of the form β€œWhat is the smallest number that is larger than x in the given list?”.


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 ( ≀ < ).


The program should print q lines. Each line should contain the answer for the corresponding query.


6 3 2 7 9 10 20 30 8 20 1
9 30 2
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.


Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue