双重和

题目描述

给定整数序列 $A = (A_1, A_2, \dots, A_N)$。

计算以下表达式:

$\displaystyle \sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)$

题目保证答案小于 $2^{63}$。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出表达式的值。

样例

3
2 5 3

4

对于 $(i, j) = (1, 2)$,有 $\max(A_j - A_i, 0) = \max(3, 0) = 3$。

对于 $(i, j) = (1, 3)$,有 $\max(A_j - A_i, 0) = \max(1, 0) = 1$。

对于 $(i, j) = (2, 3)$,有 $\max(A_j - A_i, 0) = \max(-2, 0) = 0$。

把它们加起来得到 $3 + 1 + 0 = 4$,这就是答案。

10
5 9 3 0 4 8 7 5 4 0

58

数据范围

• $2 \leq N \leq 4 \times 10^5$
• $0 \leq A_i \leq 10^8$
• 输入中的所有值均为整数。