← 返回题目列表

AtCoder · arc121_d

D. 1 或 2

中文机器翻译题面 查看原题

分数: 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