D - 1 or 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 700

問題文

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

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

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

すぬけ君は黒板に書かれた値の最大値を 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 回目の操作で美味しさ 1,2 の飴を食べ、2 回目の操作で美味しさ 4 の飴を食べるのが最適な操作手順の 1 つです。

入力例 2

2
-100 -50

出力例 2

0
  • 1 回目の操作で美味しさ -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

Score : 700 points

Problem Statement

Snuke has a blackboard and N candies. The tastiness of the i-th candy is a_i.

He will repeat the operation below until he has no more candy.

  • Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen.

Snuke wants to minimize X-Y, where X and Y are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of X-Y.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 5000
  • -10^{9} \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum possible value of X-Y, where X and Y are the largest and smallest values written on the blackboard, respectively.


Sample Input 1

3
1 2 4

Sample Output 1

1
  • One optimal sequence of operations is to eat the candies with the tastinesses of 1 and 2 in the first operation, and then eat the candies with the tastiness of 4 in the second operation.

Sample Input 2

2
-100 -50

Sample Output 2

0
  • It is optimal to eat both candies with the tastiness of -100 and -50 in the first operation.

Sample Input 3

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

Sample Output 3

13