育华学校的运动会排队问题

题目描述

育华学校即将举办运动会，各个班级需要进行方阵队列展示。有一个班级共有 $n$ 名同学，编号从 $1$ 到 $n$，每个同学有一个身高 $h_i$（$1\leq i\leq n$）。

老师希望同学们排成一排，使得队列中任意相邻两名同学的身高差的绝对值之和最小。请你计算出这个最小的身高差绝对值之和。

输入格式

第一行包含一个正整数 $n$（$2\leq n\leq 1000$），表示班级同学的数量。 第二行包含 $n$ 个正整数 $h_1, h_2, \cdots, h_n$（$1\leq h_i\leq 10000$），分别表示每个同学的身高。

输出格式

输出一个整数，表示队列中任意相邻两名同学的身高差的绝对值之和的最小值。

样例

输入样例

4
1 3 2 4

输出样例

3

解释

将同学们按身高顺序排列为 $1, 2, 3, 4$，此时相邻同学身高差的绝对值之和为 $|2 - 1|+|3 - 2|+|4 - 3| = 1 + 1+1 = 3$；若排列为 $1, 2, 4, 3$，则相邻同学身高差的绝对值之和为 $|2 - 1|+|4 - 2|+|3 - 4| = 1 + 2 + 1=4$；而排列为 $1, 3, 2, 4$ 时，相邻同学身高差的绝对值之和为 $|3 - 1|+|2 - 3|+|4 - 2|=2 + 1+2 = 5$。当排列为 $2, 1, 3, 4$ 时，相邻同学身高差的绝对值之和为 $|1 - 2|+|3 - 1|+|4 - 3|=1 + 2+1 = 4$。当排列为 $2, 3, 1, 4$ 时，相邻同学身高差的绝对值之和为 $|3 - 2|+|1 - 3|+|4 - 1|=1 + 2+3 = 6$。而最优排列是 $1, 2, 3, 4$，但更优的排列可以是 $2, 3, 4, 1$，其相邻同学身高差的绝对值之和为 $|3 - 2|+|4 - 3|+|1 - 4| = 1+1 + 3=5$，不过本题中最小的是按顺序排列 $1, 2, 3, 4$ 得到的和为 $2$ （这里假设已经经过正确的枚举或算法找到）。

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq 10$。
• 对于 $60\%$ 的数据，$2\leq n\leq 100$。
• 对于 $100\%$ 的数据，$2\leq n\leq 1000$，$1\leq h_i\leq 10000$。