P11699 [ROIR 2025] 酸雨

翻译自 [ROIR 2025 D1T3](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-regional-2025-day1.pdf)。

有 $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$。 给定一系列合并操作，请在每次合并后输出合并段的容量。

无

无

下图显示了样例中指令执行的过程，每个模块上方标出了其深度，并显示了新段的容量。  本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。 | 子任务 | 分数 | 特殊性质 | | :------: | :----: | :--------: | | $1$ | $13 $ | $n \leq 100$ | | $2 $ | $13 $ | $n \leq 1000$ | | $3 $ | $13 $ | $h_i \leq 10$ | | $4 $ | $13 $ | $\exist i,h_1 \ge h_2 \ge \dots \ge h_i \leq \dots \leq h_n$ | | $5 $ | $7 $ | 所有查询中 $k_j = 1$ | | $6 $ | $13$ | $n \leq 40000$ | | $7 $ | $28$ | 无 |