体育节 - 代码源竞赛平台

题目描述

蜗蜗准备组织一场接力赛，共有 $n$ 名选手参加，第 $i$ 名选手的速度为 $s_i$。

蜗蜗可以任意安排选手的出场顺序。在第 $i$ 个阶段，将已经出场的前 $i$ 名选手中，最大速度与最小速度的差称为这个阶段的不协调值。

请你安排选手的出场顺序，使所有 $n$ 个阶段的不协调值之和最小，并求出这个最小值。

输入格式

第一行包含一个整数 $n$，表示选手的数量。

第二行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$，表示每名选手的速度。

输出格式

输出一行一个整数，表示所有阶段的不协调值之和的最小值。

样例

4
1 2 2 5

5

样例解释

一种最优的出场顺序对应的速度依次为 $2,2,1,5$。

各阶段的不协调值依次为 $0,0,1,4$，因此总和为 $0+0+1+4=5$。

数据范围

对于 100% 的数据，保证 $1\le n\le 2000$，$1\le s_i\le 10^9$。