Lower Bound

Practice this coding question on Coding Gurukul.

Problem statement

Given an array sorted in nondecreasing order and q query values, answer each query x. For each query, print the first index i where a[i] >= x. If no such index exists, print n. Indices are zero-based. Duplicate values are allowed. Do not change the array. Use binary search in O(log n) time per query. For an empty array, print 0 for every query. Worked example For [1, 3, 3, 7, 9], queries 3, 6 and 9 give 1, 3 and 4.

Input format

First line: n q. Second line: n sorted integers (empty for n=0). Next q lines: one query value x each.

Output format

Print the result for each query on a separate line.

Constraints

0 <= n <= 100000; 1 <= q <= 100000; -10^9 <= a[i],x <= 10^9.

Sample input

5 3
1 3 3 7 9
3
6
9

Sample output

1
3
4

Sign in to run or submit a solution in C++, Java or Python.