Description

Binary search on a sorted array is an excellent algorithm: the goal is to find if there exists a[k]=key in the sorted array a[]. If found, return $k$; otherwise, return $-1$.

• If there are multiple a[k]=key, please output the largest $k$.
  
• The index $k$ starts counting from $1$.

Input Format

The first line contains an integer $N$, representing the length of the array.
The second line contains $N$ integers ($N \le 30000$) within the int range, guaranteed to be in ascending order, separated by spaces.
The third line contains an integer $T$, representing the number of queries.
The fourth line contains $T$ integers ($T \le 30000$) within the int range, representing the $key$ values to search for in each query, separated by spaces.

Output Format

A single line containing the results for each query ($k$ or $-1$), separated by spaces.

Sample

4
-2 -2 -2 1
3
-2 -2 -1

3 3 -1