You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

• 时间：1s
• 空间：512M

题面描述

在遥远的艾瑟利亚大陆上，生活着一群拥有魔法与智慧的生物——精灵。这些精灵们根据各自的天赋、属性以及能量，可以量化出一个能力值，其中第 $i$ 只精灵的能力值为 $w_i$​。

在艾瑟利亚大陆的边陲，一片被古老诅咒笼罩的幽暗之地，恶魔势力悄然崛起，威胁着整个大陆的和平与安宁。这些恶魔，由黑暗与邪恶的力量孕育而生，它们渴望吞噬光明，将艾瑟利亚拖入无尽的黑暗之中。

为了阻止恶魔势力的崛起，作为精灵之主的小哈尼希望把 $n$ 只精灵进行分组，从而在战略上增加抵御恶魔的可能性。同时，为了提高小组的灵活性，每个小组至多只能有 $2$ 只精灵。一个小组的能力值定义为该小组内所有精灵的能力值之和，为了平衡每个小组的实力，小哈尼希望能力值最大的小组的能力值减去能力值最小的小组的能力值的权值尽量小，请你告诉他这个权值至少是多少。

输入格式

从 spirit.in 文件读入数据。

输入共一行，包含一个正整数 $n$​。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $w_i$，表示第 $i$ 只精灵的能力值。

输出格式

输出到 spirit.out 文件。

输出一行，包含一个整数，表示能力值最大的小组的能力值减去能力值最小的小组的能力值的最小值。

样例

4
1 3 7 6

1

7
2 8 9 15 17 18 16

2

样例3

见选手下发目录下的 附加样例/spirit/ex_spirit3.in 和 附加样例/spirit/ex_spirit3.out 文件。

样例4

见选手下发目录下的 附加样例/spirit/ex_spirit4.in 和 附加样例/spirit/ex_spirit4.out 文件。

样例5

见选手下发目录下的 附加样例/spirit/ex_spirit5.in 和 附加样例/spirit/ex_spirit5.out 文件。

说明/提示

样例 1 解释

最优解为 $(1,7)$ 和 $(3,6)$，差值为 $1$。

样例 2 解释

最优解为 $(2,15),(8,9),(17),(18),(16)$。

评测数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 20$​。

对于 $60\%$ 的数据，$1 \leq n \leq 500$。

对于所有测评数据，$1 \leq n \leq 2 \times 10^4,-10^9 \leq w_i \leq 10^9$。