With your help, Rebecca's landscape photo is now on the cover of the latest issue of her magazine. However, some readers seem dissatisfied with the photo. In particular, they seem to think the mountain in the photo is fake!

For simplicity, we can describe this photo as a sequence of $N$ columns of pixels. In the $i$-th column, the first $h_i$ pixels from the bottom are part of the mountain. Her readers will only believe it is a real mountain if the photo contains a mountain peak. That is, if there exists an index $p$ such that $1 \le p \le N$, satisfying $h_1 \le h_2 \le \dots \le h_p \ge \dots \ge h_{N-1} \ge h_N$.

Fortunately, Rebecca can pay her editors to modify the photo and reprint the magazine. However, unfortunately for her, the editors have a very strange pricing scheme for their work. The only way Rebecca can edit the photo is by sending her editors an email containing three integers $(i, j, k)$ such that $1 \le i < j < k \le N$ and $h_i > h_j < h_k$. The editors will add an extra mountain pixel to the $j$-th column (i.e., $h_j$ increases by $1$), and the cost is $h_i + h_j + h_k$. Note that changes to $h_j$ may affect the cost of future edits.

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

Input

The first line contains an integer $N$.

The second line contains $N$ space-separated integers, representing $h_1, h_2, \dots, h_N$.

Output

Output the result modulo $10^6 + 3$, where $T$ is the minimum cost Rebecca needs to pay to please her readers.

Examples

Input 1

8
3 2 4 5 4 1 2 1

Output 1

14

Note

Rebecca can send two emails. The first email contains the three integers $(2, 6, 7)$, and the second email contains the three integers $(1, 2, 5)$. The first email costs $h_2 + h_6 + h_7 = 2 + 1 + 2 = 5$, making $h_6$ increase by $1$. The second email costs $h_1 + h_2 + h_5 = 3 + 2 + 4 = 9$, making $h_2$ increase by $1$.

The final values of $h_i$ in the photo will be $[3, 3, 4, 5, 4, 2, 2, 1]$.

Constraints

For all data, $3 \le N \le 10^6$, $1 \le h_i \le 10^9$.