背景
小猫 Rar 终于实现了自己童年的梦想，成为了一名飞行员，想带他的朋友 Dinosaur 进行几次观光飞行。Rar 生活在一个线性的世界中，这个世界可以描述为一列 N 个整数，第 i 个整数 Hi 表示从世界最左端起第 i 座山的高度。
题目描述
Rar 有 Q 架飞机，第 i 架飞机的最大巡航高度为 Yi 米。每次飞行从第 s 座山起飞，到第 e 座山降落，保证 s≤e，即 Rar 总是朝右飞行。
由于飞机有最大巡航高度，Rar 无法飞越、起飞或降落在高度大于巡航高度的山上。也就是说，若使用第 j 架飞机，Rar 只能在满足 Hi≤Yj 的山上飞行。
对于第 i 架飞机，请你帮助 Rar 计算，他一共可以进行多少次不同的飞行。也就是说，求有多少对 s,e 满足：
- 1≤s≤e≤N；
- s 到 e 之间所有山的高度均不超过该飞机的最大巡航高度。
输入格式
第一行包含两个整数 N 和 Q。
第二行包含 N 个整数 H1,H2,…,HN。
第三行包含 Q 个整数 Y1,Y2,…,YQ。
输出格式
输出 Q 行，第 i 行输出一个整数，表示使用第 i 架飞机时，Rar 可以进行的不同飞行次数。
6 3
1 3 2 4 1 2
2 3 4
5
9
21
6 3
2 2 5 2 2 2
1 2 10
0
9
21
2 1
1 2
1000000
3
提示
【样例解释】
对于样例 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≤N,Q,Hi,Yi≤106
| 子任务编号 |
分值 |
额外限制 |
| 1 |
3 |
N=2, Q=1 |
| 2 |
10 |
1≤N,Q≤30 |
| 3 |
12 |
1≤N,Q≤200 |
| 4 |
15 |
1≤N,Q≤103 |
| 5 |
1≤N≤105, Q=1, Yi=106 |
| 6 |
9 |
1≤N,Q≤105, Hi=i |
| 7 |
14 |
1≤N,Q≤105, H 严格递增 |
| 8 |
10 |
1≤N≤105, Q=1 |
| 9 |
11 |
1≤N,Q≤105 |
| 10 |
无额外限制 |
