题目描述

すぬけ君は黒板と $N$ 個の飴を持っています。 $i$ 番目の飴の おいしさ は $a_i$ です。

すぬけ君は手持ちの飴がなくなるまで、以下の操作を繰り返します。

• 手持ちの飴から $1$ つ、あるいは $2$ つ選んで食べ、その後選んだ飴のおいしさの総和を黒板に書き込む(食べた飴はなくなります)。

すぬけ君は黒板に書かれた値の最大値を $X$、最小値を $Y$ として $X-Y$ が最小になるようにしたいです。 $X-Y$ としてありうる値の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_{1}$ $a_{2}$ $\cdots$ $a_N$

输出格式

黒板に書かれた値の最大値を $X$、最小値を $Y$ とする。 $X-Y$ としてありうる値の最小値を出力せよ。

题目大意

题目描述

你有 $n$ 个糖果，第 $i$ 个糖果的美味值为 $a_i$。

你需要吃糖，每次你可以选择吃 $1$ 个或 $2$ 个糖，并将你这一次吃的糖的总和写在黑板上。

你需要求出吃完所有糖果的所有可能的情况中，黑板上数字最大值和最小值之差最小是多少。

输入格式

如原文。

输出格式

如原文。

数据范围与提示

$1\leq n\leq 5\times 10^3,-10^9\leq a_i\leq 10^9$。

---

样例一：

第一次吃第一和第二个，第二次吃第三个，黑板上的数为 $\{3,4\}$，答案为 $1$。

样例二：

第一次全部吃完，黑板上的数为 $\{-150\}$，答案为 $0$。

Translate by Zek3L.

3
1 2 4

1

2
-100 -50

0

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

13

提示

制約

• 与えられる入力は全て整数
• $1\ \leq\ N\ \leq\ 5000$
• $-10^{9}\ \leq\ a_i\ \leq\ 10^9$

Sample Explanation 1

- $1$ 回目の操作で美味しさ $1,2$ の飴を食べ、$2$ 回目の操作で美味しさ $4$ の飴を食べるのが最適な操作手順の $1$ つです。

Sample Explanation 2

- $1$ 回目の操作で美味しさ $-100,-50$ の飴を食べるのが最適です。