5426: 【83课】【3465】二分查找2

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:6 Solved:3

Description

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

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

* 下标k从1开始计数。

Input

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

第二行包含N个(N≤30000)int范围内的整数,保证升序,空格隔开。

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

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

Output

一行,对于每组询问输出结果(k 或 −1),空格隔开。 

Sample Input Copy

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

Sample Output Copy

3 3 -1