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)\).

Analysis

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 require 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 so that \(a_0 \le a_1 \le \dots \le a_{N-1}\), then for \(i < j\),
   \(|a_j - a_i| = a_j - a_i\), and we can simply add the differences without worrying about absolute values.

2. We can compute the “contribution” of each element all at once
   For a fixed \(a_i\), the sum of height differences with elements on 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 ] so if we know the left prefix sum $\sum{k=0}^{i-1} a_k\(, we can compute this in \)O(1)$.

Concrete Example

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

• \(i=0\) (150): No elements on 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\) and do the following:
   • Let \(x = a_i\) be the current value. The sum of height differences with elements on 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 can compute the contribution of each element 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, for \(i < j\) the difference is always non-negative, so we can drop the absolute value.

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

• Since the input can be large, using sys.stdin.buffer.read() allows for faster input 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.