#21001. 【模板】二分查找右端点

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hhhhan

题目描述

注意:不建议使用 std::lower_bound()std::upper_bound() 等函数。

给定一个长为 n 的数列 \{a_n\} ,保证数列非严格单调递增,即 a_i\leqslant a_{i+1}(1\le i<n)

接下来有 m 次询问,每次询问一个数 u ,请你输出 u 在数列中最右边的位置。如果在数列 \{a_n\} 中存在这样的 u ,则输出它最后出现的位置,否则输出 -1

输入格式

输入共 m+2 行。

第一行两个正整数 n,m ,代表数列长度和询问次数。

接下来一行 n 个正整数,表示非严格单调递增的数列 \{a_n\}

接下来 m 行,每行一个正整数 u ,输出它的出现的最右边的位置。

输出格式

输出共 m 行,表示每次询问的答案。

样例

5 3
1 2 2 5 5
1
3
5

1
-1
5

数据范围与提示

1\le n\le 10^5 1\le m\le 10^5 1\le a_i\le 10^9