题目描述

有一个有序且升序的数组，数组长度为 $n$。现在有 $q$ 次查询，每次查询给定一个整数 $k$，请你输出数组中最后一个小于 $k$ 的元素的位置（下标从 $1$ 开始）。如果不存在这样的元素，则输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示数组长度和查询次数。

第二行包含 $n$ 个整数，表示数组中的元素，保证数组升序排列。

接下来 $q$ 行，每行一个整数 $k$，表示一次查询。

输出格式

对于每次查询，输出一行一个整数，表示最后一个小于 $k$ 的元素的位置（下标从 $1$ 开始）。如果不存在，输出 $-1$。

5 3
1 2 3 4 5
-1
3
6

-1
2
5

样例解释

数组为 [1, 2, 3, 4, 5]。

• 查询 $k=-1$，没有小于 $-1$ 的元素，输出 $-1$；
• 查询 $k=3$，最后一个小于 $3$ 的是 $2$，位置 $2$；
• 查询 $k=6$，最后一个小于 $6$ 的是 $5$，位置 $5$。

数据范围与提示

• $1 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$
• 数组中每个元素以及 $k$ 的范围均为 $-10^9$ 到 $10^9$