Lower Bound Queries - Classic Problems | Repovive

CLS46. Lower Bound Queries

2s256 MB

Given a non-decreasing array and $q$ query values, answer each query with the first position whose value is at least the query value.

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}

Input

Explanation

The answers are positions 1, 2, 4, and -1 for the four query values.

Output

Input

Explanation

The first values not smaller than the queries are at positions 2, 4, and none.

Output

2
4
-1

Input

Explanation

All values are equal, so queries 1, 2, and 3 answer 1, 1, and -1.

Output

1
1
-1

Given a non-decreasing array and $q$ query values, answer each query with the first position whose value is at least the query value.

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}