Problem1722--二分查找-多次询问

1722: 二分查找-多次询问

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 187  Solved: 77
[Status] [Submit] [Creator:]

Description

给定一个大小为 n(1 ≤ n ≤ 106) 的整数数列 A1, A2, A3, ……,An(1 ≤ Ai ≤ 109)。数列是严格升序的,即:A1 < A2 < A3 < …… < An

有 q(1 ≤ q ≤ 106)次询问,每次询问给你一个整数 x(1 ≤ x ≤ 109),你需要判断数列中是否存在一个元素等于 x 。


Input

输入的第一行包含两个整数 n 和 q,以一个空格分隔(1 ≤ n,q ≤ 106)。

输入的第二行包含 n 个整数 A1, A2, ……, An,两两之间以一个空格分隔(1 ≤ Ai ≤ 109)。

接下来 q 行,每行包含一个整数 x(1 ≤ x ≤ 109),表示一次询问。

Output

输出共 q 行。对于每次询问的 x ,如果数列中存在一个元素等于 x ,输出这个元素对应的下标(即若存在一个 Ap = x,则输出 p);否则,输出 -1 。

Sample Input Copy

5 4
2 3 5 8 9
1
3
8
10

Sample Output Copy

-1
2
4
-1

Source/Category

 提高A