题目内容

给定 $n$ 个整数，你需要将它们任意分成两组，且两组都不能为空。

对于一组数，它的极差定义为该组中的最大值减去最小值。

设两组分别为第 $1$ 组和第 $2$ 组，则它们的极差分别为：

• 第 $1$ 组极差 $=$ 第 $1$ 组最大值 $-$ 第 $1$ 组最小值
• 第 $2$ 组极差 $=$ 第 $2$ 组最大值 $-$ 第 $2$ 组最小值

你的目标是最小化这两个极差之和，即最小化：

请输出这个最小值。

样例1

输入

5,[10,1,5,3,8]

输出

6

说明

划分为 $[10,8]$ 和 $[1,5,3]$ 两组

• 左极差 $=$ $5$-$1$ $=$ $4$
• 右极差 $=$ $10$-$8$ $=$ $2$
• 总和 $=$ $6$

样例2

输入

5,[1,1,9,1,9]

输出

0

说明

分组为 $[1,1,1]$ 和 $[9,9]$

两组的极差均为 $0$，和也为 $0$

样例3

输入

2,[1,2]

输出

0

说明

只能分为两组，每组一个数。每组的最大最小值是同一个数，极差为 $0$。