题目描述

译自 CCO 2023 Day1 T2「Real Mountains」。

在你的帮助下，Rebecca 的风景照登上了杂志封面，但部分读者认为照片中的山是假的。为了让读者信服，照片中的山必须满足“山峰”形态：存在某个下标 $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 可以通过编辑照片达到要求，编辑规则如下：

• 发送包含三个整数 $(i, j, k)$ 的电子邮件，需满足 $1 \leq i < j < k \leq N$ 且 $h_i > h_j < h_k$（$j$ 是 $i$ 和 $k$ 之间的谷点）；
• 编辑会将第 $j$ 列的山高 $h_j$ 增加 $1$，费用为操作前的 $h_i + h_j + h_k$；
• $h_j$ 的变化可能影响后续编辑的条件和费用。

你的任务是计算让照片满足山峰形态所需的最小费用 $T$。

输入格式

第一行包含一个整数 $N$（$3 \leq N \leq 10^6$），表示像素列数。

第二行包含 $N$ 个用空格分隔的整数 $h_1, h_2, \ldots, h_N$（$1 \leq h_i \leq 10^9$），表示初始时每列的山高。

输出格式

输出 $T$ 对 $10^6+3$ 取模的结果，其中 $T$ 是最小总费用。

样例

输入

8
3 2 4 5 4 1 2 1

输出

14

样例解释

Rebecca 需执行两次编辑操作：

1. 操作 $(2, 6, 7)$：满足 $h_2=2 > h_6=1 < h_7=2$，费用为 $2+1+2=5$，操作后 $h_6$ 变为 $2$；
2. 操作 $(1, 2, 5)$：满足 $h_1=3 > h_2=2 < h_5=4$，费用为 $3+2+4=9$，操作后 $h_2$ 变为 $3$。

最终山高序列为 $[3, 3, 4, 5, 4, 2, 2, 1]$，满足 $p=4$ 时的山峰形态（$3 \leq 3 \leq 4 \leq 5 \geq 4 \geq 2 \geq 2 \geq 1$），总费用 $5+9=14$。

数据范围与提示

对于所有的数据，有 $3 \leq N \leq 10^6$，$1 \leq h_i \leq 10^9$。

详细子任务附加限制及分值如下表所示：