区间和的和

题目描述

给定一个长度为 $n$ 的整数序列：

$$a_1,a_2,\ldots,a_n$$

我们把一段连续的数叫做一个区间。例如序列是 $1,2,3$ 时，$1,2$ 是一段连续的数，$2,3$ 也是一段连续的数，$1,3$ 不是一段连续的数。

一段连续的数加起来，叫做这段区间的和。

请你把所有连续区间的和都算出来，再把这些区间和加在一起。

输入格式

第一行包含一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示所有区间和的总和。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

20

输入输出样例 #2

输入 #2

5
-1 0 2 -3 4

输出 #2

9

说明/提示

样例解释 1

序列是：

1 2 3

所有连续区间一共有 $6$ 个：

区间位置	区间里的数	区间和
$[1,1]$	$1$
$[1,2]$	$1,2$	$3$
$[1,3]$	$1,2,3$	$6$
$[2,2]$	$2$
$[2,3]$	$2,3$	$5$
$[3,3]$	$3$

所以答案是：

$$1+3+6+2+5+3=20$$

样例解释 2

序列是：

-1 0 2 -3 4

把所有连续区间的和都加起来，结果为 $9$。

关于求和符号

如果你见过求和符号，也可以把题目要求写成：

$$\sum_{l=1}^{n}\sum_{r=l}^{n}(a_l+a_{l+1}+\cdots+a_r)$$

它的意思是：先选区间左端点 $l$，再选区间右端点 $r$，其中 $1\le l\le r\le n$，然后把这个区间里的数加起来。最后，把所有这样的区间和再加到一起。

限制条件

• $1 \leq n \leq 2\times 10^5$
• $-1000 \leq a_i \leq 1000$
• 输入中的数均为整数。

数据分点

子任务编号	分数	附加限制
$1$	$20$	$n \leq 50$
$2$	$30$	$n \leq 5000$
$3$	$50$	无附加限制