题目描述

你有 $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.