← 返回题目列表

AtCoder · abc351_f

I. 双倍总和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个整数序列 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}.

约束

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

输入

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

N
A_1 A_2 \dots A_N

输出

打印表达式的值。


示例输入 1

3
2 5 3

示例输出 1

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,这就是答案。


示例输入 2

10
5 9 3 0 4 8 7 5 4 0

示例输出 2

58