AT_arc121_d [ARC121D] 1 or 2

[problemUrl]: https://atcoder.jp/contests/arc121/tasks/arc121_d すぬけ君は黒板と $ N $ 個の飴を持っています。 $ i $ 番目の飴の *おいしさ* は $ a_i $ です。 すぬけ君は手持ちの飴がなくなるまで、以下の操作を繰り返します。 - 手持ちの飴から $ 1 $ つ、あるいは $ 2 $ つ選んで食べ、その後選んだ飴のおいしさの総和を黒板に書き込む(食べた飴はなくなります)。 すぬけ君は黒板に書かれた値の最大値を $ X $、最小値を $ Y $ として $ X-Y $ が最小になるようにしたいです。 $ X-Y $ としてありうる値の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_{1} $ $ a_{2} $ $ \cdots $ $ a_N $

黒板に書かれた値の最大値を $ X $、最小値を $ Y $ とする。 $ X-Y $ としてありうる値の最小値を出力せよ。

### 制約 - 与えられる入力は全て整数 - $ 1\ \leq\ N\ \leq\ 5000 $ - $ -10^{9}\ \leq\ a_i\ \leq\ 10^9 $ ### Sample Explanation 1 \- $ 1 $ 回目の操作で美味しさ $ 1,2 $ の飴を食べ、$ 2 $ 回目の操作で美味しさ $ 4 $ の飴を食べるのが最適な操作手順の $ 1 $ つです。 ### Sample Explanation 2 \- $ 1 $ 回目の操作で美味しさ $ -100,-50 $ の飴を食べるのが最適です。