题目描述

Snuke有一个黑板和$N$块糖果。第$i$块糖果的美味度为$a_i$。

他将重复以下操作，直到没有糖果可吃为止：

• 选择一块或两块糖果吃掉（当然，它们会消失）。然后，在黑板上写下他刚刚选择的糖果的总美味度。

Snuke想要最小化$X-Y$，其中$X$和$Y$分别是黑板上写下的最大值和最小值。找到$X-Y$的最小可能值。

约束条件

• 输入中的所有值都是整数。
• $1 \leq N \leq 5000$
• $-10^9 \leq a_i \leq 10^9$

输入

从标准输入读入数据，格式如下：

$N$ $a_1$ $a_2$ $\cdots$ $a_N$

输出

打印出$X-Y$的最小可能值，其中$X$和$Y$分别是黑板上写下的最大值和最小值。

示例输入 1

3
1 2 4

示例输出 1

1

• 一种最优的操作顺序是首先吃掉美味度为 $1$ 和 $2$ 的糖果，然后在第二次操作中吃掉美味度为 $4$ 的糖果。

示例输入 2

2
-100 -50

示例输出 2

0

• 最优的操作是首先吃掉美味度为 $-100$ 和 $-50$ 的两块糖果。

示例输入 3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

示例输出 3

13