Binary Search

Statement

The first line contains n, the second line contains n integers sorted in non-decreasing order. The third line contains q, the number of queries; each of the next q lines contains one integer x. For each query print on its own line the 1-based index of the first occurrence of x in the array, or -1 if it is absent.

Examples

5
1 3 5 7 9
3
5
1
4

3
1
-1

6
2 2 2 5 8 8
3
2
8
7

1
5
-1

Constraints

• 1 ≤ n, q ≤ 10^5
• -10^9 ≤ a_i, x ≤ 10^9