题目描述

在一个数组中，每个元素左边比当前元素小的所有数之和的累加值，称为该数组的小和。请编写程序计算给定数组的小和。

输入格式

• 第一行包含一个整数 $n$，表示数组的长度。
• 第二行包含 $n$ 个整数，表示数组的元素 $a_1, a_2, ..., a_n$。

输出格式

输出一个整数，表示数组的小和。

样例

5
1 3 4 2 5

16

提示

样例1解释

数组各元素的小和贡献如下： • 1：左侧无元素，贡献 $0$
• 3：左侧比 $3$ 小的数有 $[1]$，贡献 $1$
• 4：左侧比 $4$ 小的数有$[1,3]$，贡献 $4$
• 2：左侧比 $2$ 小的数有 $[1]$，贡献 $1$
• 5：左侧比 $5$ 小的数有 $[1,3,4,2]$，贡献 $10$
总和 $= 0 + 1 + 4 + 1 + 10 = 16$

数据范围

前 $60\%$ 的数据 $1\leq n \leq 2*10^3$

对于所有测试数据，保证：
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^9$