The Pair Sum Flip

**Scenario.** Sum of max(a_i, a_j) over all pairs i < j, n = 200000, values up to 10^9. What is the key insight? **Which approach is the best fit? The program only needs to print the letter.** **A)** Sort descending; the element at sorted index k is the max for exactly k pairs, contributing a[k]·k **B)** Use a Fenwick tree over values while inserting elements one by one **C)** Divide and conquer on the value range **D)** The sum is (Σa)²/2 — a pure formula