Sinulla on n omenaa, ja tiedät jokaisen omenan painon. Tehtävänäsi on jakaa omenat Uoleville, Maijalle ja Kaalepille mahdollisimman reilusti. Jaon reiluus mitataan suurimman ja pienimmän omenoiden yhteispainon erotuksena.

Syöte

Syötteen ensimmäisellä rivillä on luku n, omenoiden määrä. Toisella rivillä on n kokonaislukua, a_1, \ldots, a_n, omenoiden painot.

Tuloste

Tulosta paras mahdollinen jaon reiluus.

Rajat

• 1 \le n \le 15
• 1 \le a_i \le 10^9

Esimerkki

Syöte:

4
1 3 5 2

Tuloste:

2

Omenat kannattaa jakaa \{1, 2\}, \{3\}, \{5\} jolloin jaon reiluus on 5 - 3.

Syöte:

6
94 36 87 93 50 22

Tuloste:

21