题目描述

桌上有 $n$ 张卡片，上面的整数按非递减顺序排列，即 $a_1\le a_2\le\cdots\le a_n$，数值可以重复。

每次给出一张写有整数 $x$ 的新卡片，要求把它放在第一个数值大于等于 $x$ 的旧卡片之前。这样既保持顺序，也保证新卡片位于所有已有的 $x$ 之前。

请输出这个旧卡片的位置；如果所有旧卡片上的数都小于 $x$，输出 $n+1$，表示应放在末尾。

每次查询都只求位置，不真正插入卡片，原来的 $n$ 张卡片及其下标始终不变。位置从 $1$ 开始编号。

输入格式

第一行包含两个整数 $n,q$，分别表示旧卡片数量和查询次数。

第二行包含 $n$ 个整数，表示非递减排列的卡片数值。

接下来 $q$ 行，每行包含一个整数 $x$，表示新卡片上的数。

输出格式

输出 $q$ 行，每行一个整数，表示应插入的位置，范围为 $1$ 到 $n+1$。

4 5
10 20 20 40
20
30
50
5
40

2
4
5
1
4

1 3
-2
-3
-2
-1

1
1
2

样例 1 解释

20 应放在原来第一个 20 之前，位置是 2；30 放在原来的 40 之前，位置是 4；50 放在末尾，位置是 5。各次查询独立，因此后续查询仍使用原来的四张卡片。

样例 2 解释

新数 -3 和 -2 都应放在原卡片之前；-1 应放在末尾。

数据范围与提示

对于所有数据，$1\le n,q\le 200000$，$-10^9\le a_i,x\le 10^9$。保证卡片数值非递减。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分，总分 $100$ 分。

测试点	规模限制
1—5	$n,q\le 20$
6—10	$n,q\le 2000$
11—15	$n,q\le 50000$
16—20	$n,q\le 200000$

表中的规模限制只限制对应参数的上界，所有测试点同时满足上述完整数据范围。

时间限制：2 秒。内存限制：128 MiB。