Sum of Pair Maximums

Difficulty: 1500 3500 ms 128 MB

math sorting

Print ∑ max(a_i, a_j) over all pairs i < j.

Input: the first line has N; the second line has N integers.

Output: the total of pairwise maximums.

Constraints:

• 2 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁴

Sample Tests

3
3 1 2

8

2
7 7

7

Read the Editorial