该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

给定一个有序不递减的数组 $a$（数组中允许存在相同的元素），请你使用二分查找的方法，找出给定整数 $x$ 在数组中第一次出现的位置。

如果数组中不存在 $x$，则输出 -1。

本题中需要进行 $q$ 次查询，对每一个给定的 $x$，分别输出其在数组中第一次出现的位置。

数组下标从 1 开始计数。

格式

输入

• 第一行包含一个整数 $n$，表示数组元素的个数（$n \le 10^5$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示一个有序不递减的数组 （$1 \le a_i \le 10^8$）。
• 第三行包含一个整数 $q$，表示查询的次数（$q \le 10^5$）。
• 第四行包含 $q$ 个整数 $x_1, x_2, \dots, x_q$，表示需要查询的整数 （$1 \le x_i \le 10^8$）。

输出

• 输出一行，包含 $q$ 个整数，按输入顺序依次输出每个 $x_i$ 在数组中第一次出现的位置。
• 若某个 $x_i$ 不存在，则对应输出 -1。

样例

输入1

6
1 2 2 2 3 3
3
3 2 5

输出1

5 2 -1