题目背景

翻译自 ROIR 2025 D1T3。

题目描述

有 $n$ 个模块被运送到金星上用于组装实验室。模块按顺序排列，第 $i$ 个模块的高度为 $h_i$。

组装工作将由一台特殊的机器人来完成。在组装过程中，连续的模块段将逐渐合并，而模块在排列中的顺序不会改变。最初，每个模块都是一个独立的段，段的编号从 $1$ 到 $n$，与模块的编号顺序相同。如果有两个相邻的模块段 $A = [i, i+1, \dots, i+p-1]$ 和 $B = [i+p, i+p+1, \dots, i+p+q-1]$，那么它们合并后变成段 $AB = [i, i+1, \dots, i+p-1, i+p, i+p+1, \dots, i+p+q-1]$。

组装指令由 $n-1$ 条指令组成。每条指令包含一个数字 $k_j$。执行该指令后，编号为 $k_j$ 和 $k_j + 1$ 的模块段合并为一个新段，合并后的段占据原来两个段的位置，并重新对段进行编号，从 $k_j + 2$ 开始，后面的段的编号依次减 $1$。执行完所有指令后，所有段将合并为一个段。

金星上常年下酸雨，因此在组装过程中，必须在每次合并后了解每个段中可能积累的液体量。设一个段包含高度为 $h_l, h_{l+1}, \dots, h_r$ 的模块。对于其中任意一个模块 $p$，其中 $l \leq p \leq r$，我们定义该模块 $p$ 在该段的深度 $d_p$ 如下：

首先计算左侧最大高度 $l_p = \max\{ h_l, h_{l+1}, \dots, h_p \}$ 和右侧最大高度 $r_p = \max\{ h_p, h_{p+1}, \dots, h_r \}$。这分别是该段中模块 $p$ 左侧和右侧的最大高度。该模块 $p$ 的深度定义为 $d_p = \min(l_p, r_p) - h_p$，显然 $d_p > 0$。段的容量定义为该段所有模块的深度之和，即 $w = d_l + d_{l+1} + \dots + d_r$。

给定一系列合并操作，请在每次合并后输出合并段的容量。

输入格式

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

第二行包含 $n$ 个整数 $h_1, h_2, \dots, 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

提示

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

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。