P13075 [NOISG 2019] Pilot

小猫 Rar 终于实现了自己童年的梦想，成为了一名飞行员，想带他的朋友 Dinosaur 进行几次观光飞行。Rar 生活在一个线性的世界中，这个世界可以描述为一列 $N$ 个整数，第 $i$ 个整数 $H_i$ 表示从世界最左端起第 $i$ 座山的高度。

Rar 有 $Q$ 架飞机，第 $i$ 架飞机的最大巡航高度为 $Y_i$ 米。每次飞行从第 $s$ 座山起飞，到第 $e$ 座山降落，保证 $s \leq e$，即 Rar 总是朝右飞行。 由于飞机有最大巡航高度，Rar 无法飞越、起飞或降落在高度大于巡航高度的山上。也就是说，若使用第 $j$ 架飞机，Rar 只能在满足 $H_i \leq Y_j$ 的山上飞行。 对于第 $i$ 架飞机，请你帮助 Rar 计算，他一共可以进行多少次不同的飞行。也就是说，求有多少对 $s,e$ 满足： - $1 \leq s \leq e \leq N$； - $s$ 到 $e$ 之间所有山的高度均不超过该飞机的最大巡航高度。

第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $N$ 个整数 $H_1, H_2, \dots, H_N$。 第三行包含 $Q$ 个整数 $Y_1, Y_2, \dots, Y_Q$。

输出 $Q$ 行，第 $i$ 行输出一个整数，表示使用第 $i$ 架飞机时，Rar 可以进行的不同飞行次数。

【样例解释】 对于样例 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$ 种飞行均可进行。 【数据范围】 - $1 \leq N, Q, H_i, Y_i \leq 10^6$ | 子任务编号 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $3$ | $N = 2,\ Q = 1$ | | $2$ | $10$ | $1 \leq N, Q \leq 30$ | | $3$ | $12$ | $1 \leq N, Q \leq 200$ | | $4$ | $15$ | $1 \leq N, Q \leq 10^3$ | | $5$ | $5$ | $1 \leq N \leq 10^5,\ Q = 1,\ Y_i = 10^6$ | | $6$ | $9$ | $1 \leq N, Q \leq 10^5,\ H_i = i$ | | $7$ | $14$ | $1 \leq N, Q \leq 10^5,\ H$ 严格递增 | | $8$ | $10$ | $1 \leq N \leq 10^5,\ Q = 1$ | | $9$ | $11$ | $1 \leq N, Q \leq 10^5$ | | $10$ | $11$ | 无额外限制 |