题目描述

请在一个有序不递减的数组中（数组中的值可能相等），采用二分查找，找到值 $x$ 第一次出现的位置。如果不存在 $x$ 请输出 $-1$。

本题要求处理 $q$ 个询问，对于每个询问的 $x$，输出它在数组中第一次出现的位置。

例如：数组为 $1, 2, 2, 2, 3, 3$，询问三个数 $3, 2, 5$，它们第一次出现的位置分别是 $5, 2, -1$。

输入格式

第一行，一个整数 $n$，表示数组元素个数。
第二行，$n$ 个整数，用空格隔开，表示数组的 $n$ 个元素。
第三行，一个整数 $q$，表示询问的个数。
第四行，$q$ 个整数，用空格隔开，表示要找的数。

输出格式

一行，包含 $q$ 个整数，按题意输出每个询问的数在数组中首次出现的位置，如果不存在则输出 $-1$。整数之间用空格隔开。

样例

6
1 2 2 2 3 3
3
3 2 5

5 2 -1

数据范围

$n \le 10^5$，$q \le 10^5$，数组元素和待查找的值均在 $[1, 10^8]$ 范围内。