P2584【12月水题之王】合唱队 | |
|
Description
有N个同学参加了何老板组织的欢乐合唱队。
排练时,N个同学站成一排,但同学们高矮参差不齐,站在一起有碍观感。何老板认为,高度差比较大的两个同学站在一起是不大好看的,于是他想重新排一下队形,使得相邻两个同学的高度差的总和最小。
Input Format
第一行,一个整数N,表示有N个队员。
第二行,N个空格间隔的整数,表示每个队员的身高。
Output Format
一行,一个整数,表示高度差之和的最小值。
Sample Input
4
1 7 3 8
Sample Output
7
Hint
若采用1,7,3,8的站位方式,高度差之和为|1-7|+|7-3|+|3-8|=15
若采用8,1,3,7的站位方式,高度差之和为|8-1|+|1-3|+|3-7|=12
......
1<=N<=100000
0<队员的身高<=10000