/ 
実行時間制限: 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