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