《蔚蓝档案》（Blue Archive）是一款于 2021 年 11 月 9 日发行的收集类角色扮演游戏。在《蔚蓝档案》中，玩家扮演老师，可以带领最多六名学生参与 PvP 和 PvE 任务。玩家可以通过让学生使用特殊技能来策略性地完成任务。该游戏不仅具有游戏性，还包含解决各种问题的剧情，并因开发者与用户之间的积极沟通而获得了 2022 年韩国游戏大奖的“人气游戏奖”。

下图展示了巨型机器人与小兵对峙的场景。

你将成为一名老师，指挥学生消灭佩洛洛（Peroro）小兵。学生们将驾驶名为 KAITEN FX Mk.U 的巨型机器人来执行任务。巨型机器人从最左侧小兵的左侧开始任务。从左往右数第 $i$ 个小兵的高度为 $x_i$，巨型机器人的高度可以在任务开始前由老师设定。巨型机器人可以选择攻击它能看到的任意一个小兵。对于巨型机器人来说，要看到第 $i$ 个小兵，该小兵左侧的所有小兵高度必须严格小于巨型机器人的高度。当巨型机器人攻击一个小兵时，该小兵会完全消失，其他小兵的位置和高度保持不变。

能看到巨型机器人的小兵也会攻击它。对于第 $i$ 个小兵来说，要看到巨型机器人，该小兵左侧的所有小兵高度必须严格小于第 $i$ 个小兵的高度。你需要准备一个具有高耐久度的巨型机器人来抵御小兵的攻击。若要使用耐久度为 $K$ 的巨型机器人完成任务，在任务过程中的任何时刻（在机器人每次攻击之前），同时攻击巨型机器人的小兵数量不得超过 $K$。

你发现巨型机器人所需的耐久度取决于其高度。现给定 $Q$ 种可能的机器人高度。请编写一个程序，针对每种给定的高度，确定机器人完成任务所需的最小耐久度。

输入格式

第一行包含两个整数 $N$ 和 $Q$：小兵的数量和询问的数量（$1 \le N, Q \le 250\,000$）。

第二行包含 $N$ 个整数 $x_1, x_2, \dots, x_N$：小兵的高度，按从左到右的顺序排列（$1 \le x_i \le 10^9$）。

接下来的 $Q$ 行，每行包含一个可能的巨型机器人高度 $r_j$（$1 \le r_j \le 10^9$）。

输出格式

对于每个给定的高度 $r_j$，输出巨型机器人在该高度下完成任务所需的最小耐久度。

样例

样例输入 1

5 2
3 1 2 5 4
4
2

样例输出 1

2
3

样例输入 2

10 5
4 6 1 4 3 1 2 4 5 6
7
3
6
2
4

样例输出 2

2
5
3
5
4