分数: 466 分
问题陈述
高桥是一名城市规划测量师。沿着笔直的街道, N 建筑物鳞次栉比。它们的编号为“大楼” 1,建筑 2, ..., 建筑 N 从左到右,以及建筑物的高度 i is H_i。所有建筑物的高度都是不同的。
对于每栋建筑 i (1 \leq i \leq N),我们定义一个 “查看分数” 如下。
首先,大楼右侧的建筑物中 i (数字大于 i) 比建筑物高 i,让建筑 R_i 是最近的一个。也就是说, R_i 是最小的 j > i 这样 H_j > H_i。如果不存在这样的建筑物,那么 R_i 不存在。
同样,在大楼左侧的建筑物中 i (数字小于 i) 比建筑物高 i,让建筑 L_i 是最近的一个。也就是说, L_i 是最大的 j < i 这样 H_j > H_i。如果不存在这样的建筑物,那么 L_i 不存在。
直观上看,Building的视图得分 i 是包含 Building 的连续区间内的建筑物数量 i 向左和向右延伸,直到在每个方向上到达更高的建筑物(或街道的尽头)。具体确定如下:
- 如果两者 L_i 和 R_i 存在:分数为 R_i - L_i - 1 (建筑物之间的建筑物数量 L_i 和建筑 R_i)
- 如果只有 R_i 存在并且 L_i 不存在:分数为 R_i - 1 (来自 Building 的建筑物数量 1 前往大楼 R_i - 1)
- 如果只有 L_i 存在并且 R_i 不存在:分数为 N - L_i (来自 Building 的建筑物数量 L_i + 1 前往大楼 N)
- 如果两者都不存在:分数为 N (建筑物总数)
高桥需要回答 Q 问题。对于每个问题,一个整数 给出了 X_k 。回答 景观得分至少为的建筑物数量 X_k.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 全部 H_i 是不同的
- 1 \leq X_k \leq N (1 \leq k \leq Q)
- 所有输入值均为整数
输入
N Q H_1 H_2 \cdots H_N X_1 X_2 \vdots X_Q
- 第一行包含两个用空格分隔的整数: N,建筑物数量,以及 Q,问题数量。
- 第二行包含 N 整数 H_1, H_2, \ldots, H_N 由空格分隔,代表建筑物的高度。全部 H_i 是不同的。
- 以下 Q 行每行包含一个整数 X_k,代表每个问题的值。
输出
输出 Q 行。上 k- 第行 (1 \leq k \leq Q),输出答案 k第题,即视野得分至少为的建筑物数量 X_k.
示例输入 1
5 4 3 1 4 2 5 1 2 3 5
示例输出 1
5 3 2 1
示例输入 2
7 4 2 7 1 5 3 6 4 1 3 5 7
示例输出 2
7 3 2 1
示例输入 3
10 5 5 3 8 1 7 2 10 6 4 9 1 2 3 5 10
示例输出 3
10 6 4 2 1
示例输入 4
15 6 10 3 14 7 1 12 5 15 2 11 4 13 6 9 8 1 2 4 8 10 15
示例输出 4
15 8 4 1 1 1
示例输入 5
1 1 1000000000 1
示例输出 5
1