时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $A$，将 $A$ 的第 $l$ 位到第 $r$ 位称为子区间 $[l,r]=\{A_l,A_{l+1},...,A_r\}$，定义这个子区间的价值 $f(l,r) = \sum_{i=l}^r A_i$。

求数组 $A$ 的所有子区间的价值之和 $\sum_{i=1}^n \sum_{j=i}^n f(i,j)$。

格式

输入格式

第一行包含一个正整数 $n$，表示数组 $A$ 的长度。

第二行包含 $n$ 个正整数，表示数组 $A$。

输出格式

输出一个整数，表示数组 $A$ 的所有子区间的价值之和。

样例

样例输入 #1

4
2 3 3 3

样例输出 #1

56

数据规模

对于 $30\%$ 的数据，$n\leq 100$。

对于 $60\%$ 的数据，$n\leq 5000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$， $1\leq A_i\leq 10^3$。