問題文

岩井星人さんが、自身の主催する競技プログラミングの大会への参加希望者を募集したところ、$N$人からの応募がありました。$i$番目の応募者のレートは$R_i$です。

大会はチーム戦であり、岩井星人さんは今から次のようにチーム分けを行います。

• 任意に選んだ何人かの応募者に難癖をつけ、大会に参加させないようにする。
• 難癖をつけなかった応募者を赤チームと青チームのどちらか一方に所属させる。

各々のチーム分けにおける、あるチームの実力を、そのチームに所属する人のレートの総和で定義します。
岩井星人さんは、大会を盛り上げるため、両チームの実力をできるだけ近づけたいと思っています。岩井星人さんが最適にチーム分けを行った場合、赤チームの実力と青チームの実力の差の絶対値は最小でいくつになるか求めてください。

入力

$N$
$R_1\ R_2\ \dots\ R_N$

• $2 \leq N \leq 40$
• $0 \leq R_i \leq 8 \times 10 ^ 5$
• 入力は全て整数

出力

両チームの実力の差の絶対値が最小でいくつになるかを整数で出力してください。
最後に改行してください。

サンプル

4
1050 1100 1300 1370

20

6
0 1 2 4 8 16

1

5
1694 491 835 1875 1343

7