Binary Search

Easy#searching #binary-search· solved by 0 · time limit 2.0 s

The array is sorted and has distinct values. For each query value print its 0-based index, or -1 if it's not present. Use binary search — $O(\log n)$ per query.

Input

$n$ and the sorted array, then $q$ , then $q$ query values (one per line).

Output

One answer per line.

Constraints

$1 \le n, q \le 10^5$

Sample 1

Input

Output

3
-1
0