lower_bound

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个含有 n 个元素的递增序列(非严格递增)和 q 次询问,每次询问一个数,输出序列中第一个大于等于该数的元素的位置,如果序列中没有符合条件的数,则输出 "Not Found"。

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

对于每组数据:

  • 第 1 行输入 2 个整数 n (1 <= n <= 10^5) 和 q (1 <= q <= 10^5),表示序列长度和询问次数
  • 第 2 行输入 n 个用空格隔开的整数 Ai (0 <= Ai <= 10^9),表示这个序列
  • 接下来输入 q 行,每行输入 1 个整数 x (0 <= x <= 10^9),表示要询问的数

Output

对于每组数据中的每次询问,输出一行:如果序列中第一个大于等于该数的元素存在,则输出其位置,否则输出 "Not Found"(不包括引号)。

Sample Input

5 4
1 2 3 3 5
1
3
4
6

Sample Output

1
3
5
Not Found

Hint

示例解释:

询问 1:找到第一个大于等于 1 的数为 1,在序列中的位置为 1

询问 3:找到第一个大于等于 3 的数为 3,在序列中的位置为 3

询问 4:找到第一个大于等于 4 的数为 5,在序列中的位置为 5

询问 6:序列中无法找到任何大于等于 6 的数

 

注:数据量较大,请使用高效查找算法

Source

【2016级《程序设计基础(B)II》期末上机考试-第二场】bLue