Overview

Given the heights \(A_i\) of \(N\) people, we want to efficiently compute the sum of height differences \(|A_i-A_j|\) over all pairs \((i<j)\).

Approach

If we naively check all pairs, the number of pairs is \(\frac{N(N-1)}{2}\), resulting in \(O(N^2)\) time complexity.
Since \(N \le 2\times 10^5\), \(N^2\) would be up to about \(4\times 10^{10}\) operations, which will not finish in time (TLE).

The two key observations here are:

1. Sorting the heights removes the absolute value
   If we sort the heights in ascending order as \(a_0 \le a_1 \le \dots \le a_{N-1}\), then for \(i<j\),
   \(|a_j-a_i| = a_j-a_i\), so we can simply add the differences without worrying about absolute values.

2. We can compute each element’s “contribution” all at once
   For a fixed \(a_i\), the sum of height differences with all elements to the left (smaller values) is [ \sum_{k=0}^{i-1} (a_i - ak) ] This can be rewritten as [ \sum{k=0}^{i-1} (a_i - a_k) = i\cdot ai - \sum{k=0}^{i-1} ak ] and if we know the left prefix sum $\sum{k=0}^{i-1} a_k\(, this can be computed in \)O(1)$.

Concrete Example

For example, sort \([160, 150, 170]\) to get \([150,160,170]\).

• \(i=0\) (150): No elements to the left, so nothing to add
• \(i=1\) (160): \((160-150)=10\)
• \(i=2\) (170): \((170-150)+(170-160)=30\)

The total is \(10+30=40\), which matches the sum of absolute differences over all pairs.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Maintain a variable pref as the “running sum of elements seen so far (prefix sum)”.
3. Iterate from left to right for \(i=0..N-1\), doing the following:
   • Let the current value be \(x=a_i\). The sum of height differences with all elements to the left is
     [ x\cdot i - \text{pref} ] so add this to the answer ans.
   • Update the prefix sum with pref += x.
4. Output ans.

With this method, we compute each element’s contribution in \(O(1)\), speeding up the entire computation.

Complexity

• Time complexity: \(O(N\log N)\) (dominated by sorting; the scan is \(O(N)\))
• Space complexity: \(O(N)\) (to store the array)

Implementation Notes

• After sorting, the difference is always non-negative for \(i<j\), so we can drop the absolute value.

• ans can potentially become very large (\(A_i\) can be up to \(10^9\) and the number of pairs is large). Python’s int has arbitrary precision, so it works as-is (in other languages, 64-bit integers are required).

• Since the input can be large, using sys.stdin.buffer.read() allows for faster reading.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1+n]))
    a.sort()

    pref = 0
    ans = 0
    for i, x in enumerate(a):
        ans += x * i - pref
        pref += x

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.