#582. 徐老师的仓鼠小队
徐老师的仓鼠小队
说明
众所周知,如果养两只仓鼠,它们是会打架的那怎么办呢?再养一只,这样两只打架的时候还有一只能劝架
于是徐老师打算把自己养的 $n$ 只仓鼠三只一组放在一个笼子里养
而每只仓鼠有一个战斗力 $a_i$ 来表示第 $i$ 只仓鼠的战斗力
而一只笼子里的三只仓鼠战斗力分别为 $[x_1,x_2,x_3]$ 的话
这只笼子的安全程度即为 $max(x_1,x_2,x_3) - min(x_1,x_2,x_3)$
现在徐老师想知道,怎么分配仓鼠可以使得每只笼子的安全程度之和最小?
输入格式
第一行输入一个正整数 $n$,保证 $n$ 是 $3$ 的倍数。接下来一行输入 $n$ 个正整数 $a_i$
| 测试点编号 | $n$ | 特殊性质 |
| :---: | :---: | :---: |
| $1 \sim 2$ | $=3$ | |
| $3 \sim 4$ | $\leq 10^5$ | 所有 $a_i$ 均相等 |
| $5$ | $\leq 10^5$ | 所有 $a_i$ 均不同 |
| $6$ | $=6$ | |
| $7 \sim 8$ | $\leq 10^3$ | |
| $9 \sim 10$ | $\leq 10^5$ | |
对于所有的数据,有 $1 \leq a_i \leq 10^9$
输出格式
输出一行一个整数表示答案。样例
6
3 7 9 9 7 3
6