P10067 [CCO 2023] Real Mountains

在你的帮助下，Rebecca 的风景照现在登上了她的杂志的最新一期的封面。然而，似乎有些读者对这张照片还不满意。特别是，他们似乎认为照片中的山是假的！ 为了简单起见，我们可以把这张照片描述为一个由 $N$ 列像素组成的序列。在第 $i$ 列，从底部开始的前 $h_{i}$ 个像素是山。她的读者只有在照片中包含一个山峰时，才会相信这是一座真正的山。也就是说，如果存在某个下标 $p$，满足 $1 \leq p \leq N$，使得 $h_{1} \leq h_{2} \leq \cdots \leq h_{p} \geq \cdots \geq h_{N-1} \geq h_{N}$。 幸运的是，Rebecca 还可以付钱给她的编辑修改照片并重新印刷杂志。不过，她的倒霉的是，编辑们对他们的工作有一个非常奇怪的定价方案。Rebecca 唯一能编辑照片的方法是给她的编辑发送包含三个整数 $(i, j, k)$ 的电子邮件，满足 $1 \leq i

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格分隔的整数，表示 $h_{1}, h_{2}, \ldots, h_{N}$。

输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是 Rebecca 为了取悦她的读者而需要花费的最小费用。

Rebecca 可以发送两封电子邮件，第一封包含三个整数 $(2,6,7)$，第二封包含三个整数 $(1,2,5)$。第一封电子邮件花费 $5$，使 $h_{6}$ 增加 $1$，而第二封电子邮件花费 $9$，使 $h_{2}$ 增加 $1$。 最终照片中的 $h_{i}$ 值将是 $[3,3,4,5,4,2,2,1]$。 对于所有的数据，有 $3\leq N \leq 10^6$，$1 \leq h_{i} \leq 10^{9}$。 | 子任务编号| 分值 |$N$ 的范围 |$h_{i}$ 的范围和限制| | :-:| :-:| :-:| :-:| |1| 12| $ N \leq 5000$ |$1 \leq h_{i} \leq 100, \exists p \in [1,N], h_{1} \geq h_{2} \geq \cdots \geq h_{p} \leq \cdots \leq h_{N-1} \leq h_{N}$| |2| 12 | $ N \leq 5000$ |$1 \leq h_{i} \leq 100$| |3| 12 | $ N \leq 5000$ |$1 \leq h_{i} \leq 10^{6}$| |4| 12 | $ N \leq 5000$ |$1 \leq h_{i} \leq 10^{9}$| |5| 16 |$N \leq 10^{6}$| $1 \leq h_{i} \leq 100$| |6| 20 |$ N \leq 10^{6}$|$1 \leq h_{i} \leq 10^{6}$| |7| 16 |$ N \leq 10^{6}$|$1 \leq h_{i} \leq 10^{9}$|