Make Increasing

Given an array $A$ of $N$ natural numbers, indexed from $0$. We define $F(l, r) =$ the minimum number of operations of incrementing any element from the subarray $[l, r]$ to transform the subarray $[l, r]$ into a monotonically increasing subarray (not necessarily strictly increasing).

Task

Find $\sum_{l=0}^{N-1} \sum_{r=l}^{N-1} F(l, r)$, modulo ${2}^{32}$.

Input data

The first line will contain the nonzero natural number $N$, representing the size of the array.

The second line will contain $N$ natural numbers, separated by a single space, representing the elements of the array.

Output data

The first line will contain a single natural number, representing the required answer, modulo ${2}^{32}$.

Constraints and clarifications

• $1 \leq N \leq 1 \ 000 \ 000$;
• $0 \leq A_i < {2}^{32}$;
• Due to the very large input set, it is recommended to use fastio.
• For tests worth $5$ points: $A_i \leq A_{i+1}, \forall i \in [0, N-1)$;
• For other tests worth $10$ points: $A_i \geq A_{i+1}, \forall i \in [0, N-1)$;
• For other tests worth $15$ points: $N \leq 2\ 000$;
• For other tests worth $30$ points: $N \leq 100\ 000$, it is guaranteed that the input data is generated randomly;
• For other tests worth $20$ points: $N \leq 100\ 000$;
• For other tests worth $20$ points: no additional restrictions.

Example 1

stdin

3
10 5 1

stdout

23

Explanation

$F(0, 0) = 0$ (we do not increment anything)

$F(0, 1) = 5$ (we increment $5$ five times)

$F(0, 2) = 14$ (we increment $5$ five times and $1$ nine times)

$F(1, 1) = 0$ (we do not increment anything)

$F(1, 2) = 4$ (we increment $1$ four times)

$F(2, 2) = 0$ (we do not increment anything)

Example 2

stdin

4
1 1 3 4

stdout

0

Explanation

The entire array is already monotonically increasing, therefore all of its subarrays are already monotonically increasing.

Example 3

stdin

10
45 32 12 60 12 50 70 95 10 100

stdout

3253