Jump

A road runs left and right, and $N$ buildings stand along it. The buildings are numbered from $1$ to $N$ from left to right in the order they were built, and building $i$ has height $H_i$.

Chaewan, who has outstanding physical ability, can jump between the rooftops of two different buildings $a$ and $b$ that satisfy the following condition.

• Every building between building $a$ and building $b$ has height less than $\min(H_a, H_b)$.

Each jump costs stamina equal to the square of the difference between the two building heights. How far apart the two buildings are to the left or right does not affect the stamina cost.

Let $D(a, b)$ be the minimum total stamina needed for Chaewan to move from the rooftop of building $a$ to the rooftop of building $b$ using jumps only. Find $\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} D(i, j)$.

The first line contains the number of buildings $N$. $(2 \le N \le 500\,000)$

The second line contains the heights $H_1, H_2, \cdots, H_N$, separated by spaces. All heights are integers and are distinct. $(1 \le H_i \le 10^9)$

Print the remainder of $\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} D(i, j)$ divided by $1\,000\,000\,007$.