Description

$\hspace{15pt}$给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$，你需要计算所有区间 $[i, j]$（满足 $1 \le i \le j \le n$）的区间和的总和。

$\hspace{15pt}$形式化地说，你需要求出：

Format

Input

$\hspace{15pt}$第一行一个整数 $n(1 \le n \le 10^5)$

$\hspace{15pt}$第二行 $n$ 个整数 $a_1, a_2, \dots, a_n (-10^3 \leq a_i \leq 10^3)$

Output

$\hspace{15pt}$输出一个整数，表示所有子段和的总和。

Samples

5
1 2 3 4 5

105

3
-1 -2 -3

-20

Note

$\hspace{15pt}$对于第一组样例，每一个区间和如下：

$\hspace{15pt}$[1] = 1 , [2] = 2 , [3] = 3 , [4] = 4 , [5] = 5

$\hspace{15pt}$[1,2] = 3 , [2,3] = 5 , [3,4] = 7 , [4,5] = 9

$\hspace{15pt}$[1,2,3] = 6 , [2,3,4] = 9 , [3,4,5] = 12

$\hspace{15pt}$[1,2,3,4] = 10 , [2,3,4,5] = 14

$\hspace{15pt}$[1,2,3,4,5] = 15

$\hspace{15pt}$总和为 105。

$\hspace{15pt}$对于第二组样例，经同样的计算可得结果为 -20。