P10067 [CCO 2023] Real Mountains

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

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

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

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}$. | Subtask ID | Score | Range of $N$ | Range and constraints on $h_{i}$ | | :-: | :-: | :-: | :-: | | 1 | 12 | $N \leq 5000$ | $1 \leq h_{i} \leq 100, \exists p \in [1,N], h_{1} \geq h_{2} \geq \cdots \geq h_{p} \leq \cdots \leq h_{N-1} \leq h_{N}$ | | 2 | 12 | $N \leq 5000$ | $1 \leq h_{i} \leq 100$ | | 3 | 12 | $N \leq 5000$ | $1 \leq h_{i} \leq 10^{6}$ | | 4 | 12 | $N \leq 5000$ | $1 \leq h_{i} \leq 10^{9}$ | | 5 | 16 | $N \leq 10^{6}$ | $1 \leq h_{i} \leq 100$ | | 6 | 20 | $N \leq 10^{6}$ | $1 \leq h_{i} \leq 10^{6}$ | | 7 | 16 | $N \leq 10^{6}$ | $1 \leq h_{i} \leq 10^{9}$ | Translated by ChatGPT 5