B. Bytelandia's stones
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical Academy of Bytelandia, an archmage is studying a line of $$$n$$$ enchanted stones, each with a power value $$$a_1, a_2, \ldots, a_n$$$.

A query spell is defined as follows: for two indices $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq n$$$), the spell reveals the total power of the stones from position $$$L$$$ to $$$R$$$:

$$$$$$ S(L,R) = \sum_{i=L}^{R} a_i $$$$$$

The oracle wonders: what is the total sum of the answers of all possible queries?

Formally, compute:

$$$$$$\left( \sum\limits_{L=1}^N \sum\limits_{R=L}^N S(L, R) \right)$$$$$$

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of stones.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^3$$$) — the values of the stones.

Output

Print a single integer: the total sum of all queries.

Examples
Input
3
1 2 3
Output
20
Input
5
3 4 7 1 3
Output
133
Input
3
1 10 100
Output
343