折半查找

题目描述

给定一个严格升序整数序列 $a_1,a_2,\dots,a_n$（没有相同元素）。并给出 $q$ 次询问，每次询问一个整数 $x$，要求输出它在序列中的下标。请使用折半查找算法。

输入

第一行两个整数 $n, q$。分别表示序列长度和询问次数。$1\leq n,q\leq 10^5$。

第二行空格隔开的 $n$ 个整数 $a_i$，均在 int 范围内。保证没有相同元素，且以升序给出。

接下来 $q$ 行，每行一个整数 $x$ 表示询问的数字。如果该数字在序列中出现，输出其下标，否则输出 "tan90"（不含引号）。

输出

对于每次询问，输出一行一个整数，表示答案。

输入样例

5 4
-3 0 1 45 100
1
-3 
-1
100

输出样例

3
1
tan90
5

来源

课件 $40\sim 44$ 页。注意不要超过时间限制。