In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 26th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #03 exercise sheet]


[AED005] Number Searching

Tom has a sequence of sorted integer numbers and he is sure there should be a way look for them better than just using a linear search... he needs your help for that!

The Problem

Given a sorted sequence of N distinct integer numbers and Q queries, each one indicating a number to search for, your task is to find the position of each query number in the sequence (or to find that it does not appear in the sequence).

Input

The first line of the input contains an integer N, the quantity of numbers in the sorted sequence. The second line contains the sequence itself with N space separated integers (we denote each one by Si). It is guaranteed that these numbers are distinct and that they come in increasing order.

The third line contains an integer Q, the quantity of queries to consider. Each of the following Q lines contains a query in the form of a single integer Xi, indicating the number we are searching for.

Output

The output should contain exactly Q lines. The i-th line should contain the position of the number Xi in the sequence or -1 is the number does not appear. Note that the positions in the sequence go from 0 to N-1.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ N ≤ 105       Quantity of numbers in the sequence
1 ≤ Si ≤ 109       Numbers in the sorted sequence
1 ≤ Q ≤ 105       Quantity of queries
1 ≤ Xi ≤ 109       Numbers that will be queried

Example Input Example Output
8
2 7 10 12 13 14 42 105
7
2
105
42
28
1
13
999
0
7
6
-1
-1
4
-1

Explanation of the example:


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto