题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

你需要计算出数列中任意两个元素数值之差的绝对值之和。即计算：

$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} |a_i - a_j| = |a_1 - a_2| + |a_1 - a_3| + \ldots + |a_{n-1} - a_n|$

输入格式

第一行，一个整数 $n(2 \le n \le 10^6)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^6)$。

输出格式

输出一个整数，表示数列中任意两个元素数值之差的绝对值之和。

3
1 2 3

4

5
6 2 1 5 4

26

说明/提示

样例解释

• 样例1：$|a_1 - a_2| + |a_1 - a_3| + |a_2 - a_3| = |1 - 2| + |1 - 3| + |2 - 3| = 4$
• 样例2：$|a_1 - a_2| + |a_1 - a_3| + |a_1 - a_4| + |a_1 - a_5|$ $+ |a_2 - a_3| + |a_2 - a_4| + |a_2 - a_5| + |a_3 - a_4| + |a_3 - a_5| + |a_4 - a_5|$ $= |6-2| + |6-1| + |6-5| + |6-4| + |2-1|$ $+ |2-5| + |2-4| + |1-5| + |1-4| + |5-4|$ $= 26$

数据规模与约定

• 对于 $20\%$ 的数据，$n, a_i \le 100$
• 对于 $40\%$ 的数据，$n, a_i \le 1000$
• 对于 $60\%$ 的数据，$n, a_i \le 10^4$
• 对于 $80\%$ 的数据，$n, a_i \le 10^5$
• 对于 $100\%$ 的数据，$2 \le n \le 10^6,1 \le a_i \le 10^6$