Problem Description

With your help, Rebecca’s landscape photo has made it onto the cover of the latest issue of her magazine. However, some readers still seem unhappy with the photo. In particular, they think the mountains in the photo are fake.

For simplicity, we can describe the photo as a sequence of $N$ columns of pixels. In column $i$, the bottom $h_{i}$ pixels are mountain. Her readers will only believe this is a real mountain if the photo contains a single peak. That is, if there exists an index $p$ with $1 \leq p \leq N$ such that $h_{1} \leq h_{2} \leq \cdots \leq h_{p} \geq \cdots \geq h_{N-1} \geq h_{N}$.

Luckily, Rebecca can also pay her editors to modify the photo and reprint the magazine. Unfortunately, the editors have a very strange pricing scheme for their work. The only way Rebecca can edit the photo is to send her editors an email containing three integers $(i, j, k)$ satisfying $1 \leq i<j<k \leq N$ and $h_{i}>h_{j}<h_{k}$. The editors will add one extra mountain pixel to column $j$ (i.e., increase $h_{j}$ by $1$), at a cost of $h_{i}+h_{j}+h_{k}$. Note that changes to $h_{j}$ may affect the cost of future edits.

To satisfy her readers, Rebecca wants to edit the photo so that they believe there is a real mountain here. Can you tell her the minimum total cost required?

Input Format

The first line contains an integer $N$.

The second line contains $N$ space-separated integers, denoting $h_{1}, h_{2}, \ldots, h_{N}$.

Output Format

Output $T \bmod (10^{6}+3)$, where $T$ is the minimum total cost Rebecca needs to pay to satisfy her readers.

8
3 2 4 5 4 1 2 1

14

Hint

Rebecca can send two emails. The first contains $(2,6,7)$, and the second contains $(1,2,5)$. The first email costs $5$ and increases $h_{6}$ by $1$, and the second email costs $9$ and increases $h_{2}$ by $1$.

In the end, the $h_{i}$ values in the photo will be $[3,3,4,5,4,2,2,1]$.

For all testdata, $3\leq N \leq 10^6$ and $1 \leq h_{i} \leq 10^{9}$.

Translated by ChatGPT 5