Sum of Pair Minimums

Difficulty: 1500 3500 ms 128 MB

math sorting

Print ∑ min(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 minimums.

Constraints:

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

Sample Tests

3
3 1 2

4

2
7 7

7

Read the Editorial