After receiving a picture of a lollipop from Little P, Little W thought it was so "lollipop-tastic" that he reciprocated with a less "lollipop-tastic" colored ribbon.
Little W adds brightness and darkness to the colored ribbon to make it more beautiful.
For a colored ribbon consisting of $m$ cells, the coloring difficulty $f(a)$ to dye the ribbon into a brightness-darkness sequence $a$ of length $m$ is defined as follows:
- Initially, the darkness of each cell on the ribbon is $0$.
You can perform several operations. In each operation, you must:
- Fold the ribbon along the dividing line between any two cells. The folding operation can be performed multiple times, or not at all.
- Choose a position to drop black dye. The dye will penetrate from the top and flow downwards, increasing the darkness of all cells in its path by $1$. After dropping the dye, unfold the ribbon.
$f(a)$ represents the minimum number of operations required such that the darkness of all positions where $a_i > 0$ is $\ge a_i$, and the darkness of all positions where $a_i = 0$ is exactly $0$.
Now, Little W has a colored ribbon of length $n$ and a candidate brightness-darkness sequence $b$ of length $n$. He has not yet decided which brightness-darkness pattern looks best, so he wants you to calculate the sum of the coloring difficulties for all sub-intervals $[l, r]$ of $b$, where the ribbon consists of $r-l+1$ cells. Formally, you need to calculate $\sum\limits_{1\le l\le r\le n}f(b[l, r])$.
Output the answer modulo $2^{64}$.
Input Format
The first line contains a positive integer $n$.
The next line contains $n$ non-negative integers $b_1, b_2, \dots, b_n$.
Output Format
A non-negative integer representing the answer modulo $2^{64}$.
Constraints
| Test Case ID | Score | Additional Constraints |
|---|---|---|
| 1 | 5 | $b_i > 0$ |
| 2 | 5 | $b_i > 0$ |
| 3 | 5 | Number of $b_i > 0$ does not exceed $300$ |
| 4 | 5 | Number of $b_i > 0$ does not exceed $300$ |
| 5 | 5 | $n \le 15$ |
| 6 | 5 | $n \le 15$ |
| 7 | 5 | $n \le 500$ |
| 8 | 5 | $n \le 500$ |
| 9 | 5 | $n \le 500$ |
| 10 | 5 | $n \le 500$ |
| 11 | 5 | $n \le 5000$ |
| 12 | 5 | $n \le 5000$ |
| 13 | 5 | $n \le 5000$ |
| 14 | 5 | $n \le 5000$ |
| 15 | 5 | $n \le 50000$ |
| 16 | 5 | $n \le 50000$ |
| 17 | 5 | None |
| 18 | 5 | None |
| 19 | 5 | None |
| 20 | 5 | None |
For all data: $1 \le n \le 10^6, 0 \le b_i \le 10^9$.
Examples
Input 1
3 1 0 2
Output 1
9
Input 2
6 2 0 1 3 0 1
Output 2
51
Input 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
Output 3
993