Norma's array price sum

Mirko got an array of integers from his grandmother Norma for his birthday. Like any other kid he was hoping for money, but he got an array. Luckily, the town he lives in has a pawn shop that buys arrays.

The price of an array of integers is $\min \times \max \times L$ kuna, where $\min$ is the smallest integer in the array, $\max$ is the largest one, and $L$ is the length of the array.

Mirko wants to sell one subarray of consecutive elements of his array. While he was deciding which one, he added up the prices of every subarray he could sell. He asks you for the same value so he can check his arithmetic.

Only the last nine digits of the sum matter, so you do not have to work with huge or real numbers.

The first line contains an integer $N$ ($1 \le N \le 500\,000$).

Each of the next $N$ lines contains one element of Mirko's array, in order. Every element is an integer between $1$ and $10^8$.

Print the last nine digits of the sum of the prices of all subarrays of consecutive elements, as a single integer on one line. In other words, print that sum modulo $10^9$. Do not print leading zeroes.

In the first example the array holds the integers $1$ and $3$. The subarrays Mirko can sell are $(1)$, $(3)$, $(1, 3)$, and their prices are $1$, $9$, $6$, which add up to $16$.

In the second example the subarrays Mirko can sell are $(2)$, $(4)$, $(1)$, $(4)$, $(2, 4)$, $(4, 1)$, $(1, 4)$, $(2, 4, 1)$, $(4, 1, 4)$, $(2, 4, 1, 4)$, and their prices are $4$, $16$, $1$, $16$, $16$, $8$, $8$, $12$, $12$, $16$, which add up to $109$.