题目描述

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

* 若有多个a[k]=key，请输出最大的$k$。

* 下标k从1开始计数。

输入

第一行包含1个整数$N$，代表数组长度。

第二行包含$N$个int范围内的整数，保证升序，空格隔开。

第三行包含1个整数$T$，代表有$T$组询问。

第四行包含$T$个int范围内的整数，表示每组询问需要查找的$key$值，空格隔开。

输出

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

样例

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

3 3 -1

数据范围

对于100% 的数据;$N≤30000;T≤30000$

来源

• 一本通编程启蒙在线评测