题目描述

对有序数组进行二分查找，是一种性能卓越的算法：目标是在有序数组 $a[ ]$ 中查找是否有 $a[k] = key$ ，若有返回 $k$ ，否则返回 $-1$ 。

• 若有多个 $a[k]=key$ ，请输出最右侧的 $k$ 。
  
• 下标 $k$ 从 $0$ 开始计数。

输入格式

第一行包含 $1$ 个整数 $N$ ，代表数组长度。
第二行包含 $N$ 个（ $N \le 30000$ ）int 范围内的整数，空格隔开。
第三行包含 $1$ 个整数 $T$ ，代表有 $T$ 组询问。
第四行包含 $T$ 个（ $T \le 30000$ ）int 范围内的整数，表示每组询问需要查找的 $key$ 值，空格隔开。

输出格式

一行，对于每组询问输出结果（k or -1），空格隔开。

样例

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

1 1 -1

10
1 1 1 1 1 2 2 3 3 5
5
1 1 2 3 5

4 4 6 8 9