Rar the Cat 终于实现了他儿时的飞行员梦想，并想带着他的朋友 Dinosaur 进行几次观光飞行。Rar 生活在一个线性世界中，这个世界可以用 $N$ 个整数来描述，其中第 $i$ 个整数 $H_i$ 表示第 $i$ 座山相对于他世界最左侧边缘的高度。
例如，当 $N = 6, H = \{1, 3, 2, 4, 1, 2\}$ 时，这个世界看起来像这样：
Rar 总共有 $Q$ 架飞机想要展示，其中第 $i$ 架飞机的最大巡航高度为 $Y_i$ 米。每次飞行从第 $s$ 座山开始，在第 $e$ 座山结束。我们可以假设 $s \le e$，即 Rar 总是向右飞行。由于他的每架飞机都有最大巡航高度，他无法飞越、起飞或降落在高度大于其巡航高度的山上，即 Rar 仅能在第 $j$ 架飞机满足 $H_i \le Y_j$ 的情况下飞越第 $i$ 座山。
对于第 $i$ 架飞机，请帮助 Rar 确定他可能采取的飞行总数，即 Rar 选择 $s$ 和 $e$ 使得 $s \le e$ 且在 $s$ 到 $e$（包含端点）之间没有高度大于 $Y_i$ 的山的总方案数。
输入格式
程序必须从标准输入读取数据。 第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $N$ 个整数 $H_1, \dots, H_N$。 第三行包含 $Q$ 个整数 $Y_1, \dots, Y_Q$。
输出格式
程序必须输出到标准输出。 输出应包含 $Q$ 行，每行一个整数，第 $i$ 行的数字表示 Rar 使用第 $i$ 架飞机可以采取的飞行总数。
数据范围
对于所有测试用例，输入满足以下限制： * $1 \le N, Q, H_i, Y_i \le 10^6$
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 3 | $N = 2, Q = 1$ |
| 2 | 10 | $1 \le N, Q \le 30$ |
| 3 | 12 | $1 \le N, Q \le 200$ |
| 4 | 15 | $1 \le N, Q \le 10^3$ |
| 5 | 5 | $1 \le N \le 10^5, Q = 1, Y_i = 10^6$ |
| 6 | 9 | $1 \le N, Q \le 10^5, H_i = i$ |
| 7 | 14 | $1 \le N, Q \le 10^5, H$ 严格递增 |
| 8 | 10 | $1 \le N \le 10^5, Q = 1$ |
| 9 | 11 | $1 \le N, Q \le 10^5$ |
| 10 | 11 | - |
样例
样例输入 1
6 3 1 3 2 4 1 2 2 3 4
样例输出 1
5 9 21
说明 1
对于第一架飞机，有 5 种可能的飞行：(1, 1), (3, 3), (5, 5), (5, 6), (6, 6)。对于第二架飞机，有 9 种可能的飞行：(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (5, 5), (5, 6), (6, 6)。对于最后一架飞机，所有 21 种飞行都是可能的。
样例输入 2
6 3 2 2 5 2 2 2 1 2 10
样例输出 2
0 9 21
样例输入 3
2 1 1 2 1000000
样例输出 3
3