Zonal Computing Olympiad 2013, 10 Nov 2012
N teams participate in a league cricket tournament on Mars, where each pair of distinct teams plays each other exactly once. Thus, there are a total of (N × (N-1))/2 matches. An expert has assigned a strength to each team, a positive integer. Strangely, the Martian crowds love one-sided matches and the advertising revenue earned from a match is the absolute value of the difference between the strengths of the two matches. Given the strengths of the N teams, find the total advertising revenue earned from all the matches.

For example, suppose N is 4 and the team strengths for teams 1, 2, 3, and 4 are 3, 10, 3, and 5 respectively. Then the advertising revenues from the 6 matches are as follows:

Match Team A Team B Ad revenue 1 1 2 7  2 1 3 0  3 1 4 2  4 2 3 7  5 2 4 5  6 3 4 2 

Thus the total advertising revenue is 23.

-----Input format-----
Line 1 : A single integer, N.
Line 2 : N space-separated integers, the strengths of the N teams.

-----Output format-----
A single integer, the total advertising revenue from the tournament.

-----Sample input-----
4
3 10 3 5

-----Sample output-----
23

-----Test data-----
In all subtasks, the strength of each team is an integer between 1 and 1,000 inclusive.
- Subtask 1 (30 marks) : 2 ≤ N ≤ 1,000.
- Subtask 2 (70 marks) : 2 ≤ N ≤ 200,000.

-----Live evaluation data-----
- Subtask 1: Testcases 0,1,2.
- Subtask 2: Testcases 3,4,5.

-----Note-----
The answer might not fit in a variable of type int. We recommend that type long long be used for computing all advertising revenues. If you use printf and scanf, you can use %lld for long long.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def abs(x): \n    if x < 0:\n        return -x\n    else: \n        return x\n\n# cook your dish here\nprecalculated = {}\nN = int(input())\ntmp = input() \nwhile(tmp[-1] == " "): \n    tmp = tmp[:-1]\nvalues = list(map(int, tmp.split(" ")))\ntotal = 0\nsaved_sum = sum(values) \nsaved_length = len(values) - 1\nfor val in values:\n    if val in precalculated:\n         precalculated[val][1] += 1\n    else: \n        precalculated[val] = [0, 1]\nfor pre in precalculated:\n    for pre1 in precalculated: \n        precalculated[pre][0] += precalculated[pre1][1] * abs(pre1 - pre)\nfor pre in precalculated: \n    total += precalculated[pre][0] * precalculated[pre][1]\n\nprint(total // 2)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13567