题目描述

农夫约翰（Farmer John）收到了邻居农夫鲍勃（Farmer Bob）的噪音投诉，称他的奶牛们叫声太大。

FJ 的 $N$ 头奶牛（$1 \leq N \leq 10,000$）分散在一个一维草场的不同位置。这些奶牛非常健谈，每一对奶牛都在同时进行对话（因此每头奶牛都在同时向其他 $N-1$ 头奶牛发出“哞”声）。当奶牛 $i$ 向奶牛 $j$ “哞”叫时，其音量必须等于两者之间的距离 $|x_i - x_j|$，这样奶牛 $j$ 才能听到。请帮助 FJ 计算所有 $N \times (N-1)$ 次“哞”叫产生的总音量。

输入格式

• 第 $1$ 行：一个整数 $N$（奶牛数量）。
• 第 $2$ 行到第 $N+1$ 行：每行一个整数，表示每头奶牛的位置（范围 $0 \leq x_i \leq 1,000,000,000$）。

输出格式

• 一个整数，表示所有“哞”叫的总音量。

示例输入 1

5
1
5
3
2
4

示例输出 1

40

提示

输入解释：
$5$ 头奶牛的位置分别为 $1, 5, 3, 2, 4$。

输出解释：

• 位于 $1$ 的奶牛贡献 $|1-5| + |1-3| + |1-2| + |1-4| = 4 + 2 + 1 + 3 = 10$。
• 位于 $5$ 的奶牛贡献 $|5-1| + |5-3| + |5-2| + |5-4| = 4 + 2 + 3 + 1 = 10$。
• 位于 $3$ 的奶牛贡献 $|3-1| + |3-5| + |3-2| + |3-4| = 2 + 2 + 1 + 1 = 6$。
• 位于 $2$ 的奶牛贡献 $|2-1| + |2-5| + |2-3| + |2-4| = 1 + 3 + 1 + 2 = 7$。
• 位于 $4$ 的奶牛贡献 $|4-1| + |4-5| + |4-3| + |4-2| = 3 + 1 + 1 + 2 = 7$。
  总音量为 $10 + 10 + 6 + 7 + 7 = 40$。

题目来源

USACO 2005 January Silver