You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

U 宇宙发现了能用于快速星际穿行的 u 元素，U 宇宙有 $n$ 个行星，第 $i$ 个行星的 u 元素含量为 $u_i$（$u_i$ 可以是负数），搭建行星 $1\leq i < j\leq n$ 间利用 u 元素的快速通行轨道的代价为 $u_j - u_i$，为保证连通性，U 宇宙需要让新铺设的 u 元素轨道使得各行星连成一棵树。

那么满足要求的最少代价是多少呢？

输入格式

输入的第一行包含一个整数 $n$，表示 U 宇宙的行星数。

接下来一行，包含 $n$ 个整数 $u_1,u_2,\cdots, u_n$，表示各行星的 u 元素含量。

输出格式

输出一行一个整数，表示符合题意的最小代价。

8
-3 5 -1 2 0 4 6 3

-18

3
1 2 3

2

附加样例

b.in
b.out

数据范围与提示

对于所有数据，$1 \le n \le 3 \times 10^5$，$-300\,000 \le u_i \le 300\,000$.