Binary search 3 - MarisaOJ: Marisa Online Judge

You are given: - An integer non-decreasing array

$A$ of

$n$ integers. -

$q$ queries, each is an integer

$x$ , find the biggest

$i$ that

$A_i \le x$ . ### Input - The first line contains 2 integer

$n, q$ . - The second line contains

$n$ space-separated integers

$A_i$ . - The next

$q$ lines, each contains an single integer

$x$ , a query. ### Output - Print

$q$ lines,

$i^{th}$ line is the answer to query

$i$ . Print

$-1$ no position can be found. ### Constraints -

$1 \le n, q \le 10^{5}$ . -

$1 \le A_i \le 10^9$ . ### Example Input:

$5 3 1 2 3 3 9 1 5 3$

Output:

$1 4 4$

Topic

Binary search

Rating

800

Solution (0)

Solution