感谢您在裁剪照片方面的帮助，Rebecca 的风景照现在登上了她杂志最新一期的封面。然而，似乎仍有一些读者对这张照片不满意。特别是，他们似乎认为照片里的山是假的！
为了简化起见，我们可以将这张照片描述为 $N$ 列像素的序列。在第 $i$ 列中，从底部开始的前 $h_i$ 个像素是山脉。只有当照片包含单个（可能是宽的）山峰时，读者才会相信照片中包含真正的山脉。也就是说，如果存在某个索引 $p$（$1 \le p \le N$），使得 $h_1 \le h_2 \le \dots \le h_p \ge \dots \ge h_{N-1} \ge h_N$。
幸运的是，Rebecca 仍然可以付费请编辑修改照片并重新印刷杂志。但遗憾的是，编辑们有一套非常奇特的定价方案。Rebecca 修改照片的唯一方式是给编辑发送包含整数 $(i, j, k)$ 的电子邮件，其中 $1 \le i < j < k \le 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, \dots, h_N$。
子任务
| 分值 | $N$ 的范围 | $h_i$ 的范围及约束 |
|---|---|---|
| 3 分 | $3 \le N \le 5\,000$ | $1 \le h_i \le 100$；对于某个 $p$ ($1 \le p \le N$)，满足 $h_1 \ge h_2 \ge \dots \ge h_p \le \dots \le h_{N-1} \le h_N$ |
| 3 分 | $3 \le N \le 5\,000$ | $1 \le h_i \le 100$ |
| 3 分 | $3 \le N \le 5\,000$ | $1 \le h_i \le 10^6$ |
| 3 分 | $3 \le N \le 5\,000$ | $1 \le h_i \le 10^9$ |
| 4 分 | $3 \le N \le 10^6$ | $1 \le h_i \le 100$ |
| 5 分 | $3 \le N \le 10^6$ | $1 \le h_i \le 10^6$ |
| 4 分 | $3 \le N \le 10^6$ | $1 \le h_i \le 10^9$ |
输出格式
输出 $T$ 除以质数 $10^6 + 3$ 的余数，其中 $T$ 是 Rebecca 为取悦读者所需支付的最低成本（以美分为单位）。
样例
样例输入 1
8 3 2 4 5 4 1 2 1
样例输出 1
14
说明 1
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]$。她的读者将会相信这张最终的照片包含一座真正的山脉。