题目描述

在你的帮助下，Rebecca 的风景照登上了杂志最新一期的封面。然而，一些读者仍然不满意：他们认为照片里的山是假的。

为了简单起见，我们把这张照片描述成一个由 $N$ 列像素组成的序列。在第 $i$ 列，从底部开始的前 $h_i$ 个像素是山。

读者只有在照片中包含一座“真正的山峰”时，才会相信这是一座真正的山。也就是说，如果存在某个下标 $p$，满足 $1\le p\le N$，使得

$$h_1\le h_2\le \cdots \le h_p\ge \cdots \ge h_{N-1}\ge h_N,$$

那么这张照片就会被认为包含一座真正的山。

幸运的是，Rebecca 还可以付钱给编辑修改照片并重新印刷杂志。不过，编辑们的定价方案非常奇怪。Rebecca 唯一能编辑照片的方法是给编辑发送一封包含三个整数 $(i,j,k)$ 的电子邮件，满足

$$1\le i<j<k\le N,\qquad 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\le N\le 10^6,\qquad 1\le h_i\le 10^9.$$

子任务编号	分值	$N$ 的范围	$h_i$ 的范围和限制
1	12	$3\le N\le 5000$	$1\le h_i\le 100$，且存在 $p\in[1,N]$，使得 $h_1\ge h_2\ge\cdots\ge h_p\le\cdots\le h_{N-1}\le h_N$
2			$1\le h_i\le 100$
3			$1\le h_i\le 10^6$
4			$1\le h_i\le 10^9$
5	16	$3\le N\le 10^6$	$1\le h_i\le 100$
6	20		$1\le h_i\le 10^6$
7	16		$1\le h_i\le 10^9$