题目描述

译自 ROI Regional 2025 Day1 T3. Кислотные дожди

为了在金星上建造实验室定居点，运送了 $n$ 个模块。这些模块按顺序排列，第 $i$ 个模块的高度为 $h_i$。

组装将由一个特殊的机器人完成。在组装过程中，连续的模块段将逐渐合并，而模块的顺序不会改变。

最初，每个模块都是一个独立的段，这些段按从 $1$ 到 $n$ 的顺序编号。如果有两个相邻的段由模块组成：段 $A = [i, i+1, \ldots, i+p-1]$ 和段 $B = [i+p, i+p+1, \ldots, i+p+q-1]$，那么它们合并后得到段 $AB = [i, i+1, \ldots, i+p-1, i+p, i+p+1, \ldots, i+p+q-1]$。

组装说明由 $n-1$ 条指令组成。每条指令由一个数字 $k_j$ 表示。执行此指令后，编号为 $k_j$ 和 $k_j + 1$ 的段合并为一个段，合并后的段占据原来两个段的位置，并重新对段进行编号，编号从 $k_j + 2$ 开始递减 $1$。执行完所有指令后，所有段将合并为一个段。

在金星上常年下酸雨，因此在组装过程中，了解每个模块段可以积聚多少液体非常重要。假设段由高度为 $h_l, h_{l+1}, \ldots, h_r$ 的模块组成。对于 $p$，其中 $l \le p \le r$，我们定义该段中高度为 $h_p$ 的模块的深度如下。计算 $l_p = \max \{ h_l, \ldots, h_p \}$ 和 $r_p = \max \{ h_p, \ldots, h_r\}$，这是段中$p$左侧和右侧的最高模块。然后，段中模块 $p$ 的深度为 $d_p = \min(l_p, r_p) - h_p$，注意 $d_p \ge 0$。容量指的是该段所有模块深度的总和，即 $w = d_l + d_{l+1} + \ldots + d_r$。

给定一系列段合并指令。每次合并后输出合并段的容量。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$，表示模块的数量 。

第二行包含 $n$ 个整数 $h_1, \ldots, h_n$ $(1 \leq h_i \leq 10^9)$。

第三行包含 $n - 1$ 个整数，表示段合并指令。每条指令由一个整数 $k_j$ $(1 \leq k_j \leq n - j)$ 表示。

输出格式

输出 $n-1$ 个整数，每次合并后输出合并段的容量。

8
9 1 8 1 5 2 3 6
3 3 1 3 3 2 1

0
4
0
0
0
13
20

下图显示了样例中指令执行的过程，每个模块上方标出了其深度，并显示了新段的容量。

数据范围与提示

详细子任务附加限制及分值如下表所示。