题目描述

请在一个有序不递减的数组中（数组中的值可能相等），采用二分查找，找到值 $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

数据范围与提示

• $1 \le n \le 10^5$
• $1 \le q \le 10^5$
• 数组元素和待查找的值均满足 $1 \le x \le 10^8$