分数: 700 点
问题陈述
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