题目描述

在你的帮助下，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<j<k \leq N$ 且 $h_{i}>h_{j}<h_{k}$。编辑们会在第 $j$ 列添加一个额外的山的像素（即 $h_{j}$ 增加 $1$），费用是 $h_{i}+h_{j}+h_{k}$。注意 $h_{j}$ 的变化可能会影响未来编辑的费用。

为了取悦她的读者，Rebecca 想要编辑照片，让他们相信这里有一座真正的山。你能告诉她需要花费的最小费用吗？

输入格式

第一行包含一个整数 $N$。

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

输出格式

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

8
3 2 4 5 4 1 2 1

14

提示

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}$。