Pour une séquence $a_{1 \dots n}$, on définit $f(a)$ comme $$f(a) = \max_{1 \le l \le r \le n} \sum_{i=l}^r a_i.$$

Étant donné une séquence $b_{1 \dots n}$, vous devez permuter $b_{1 \dots n}$ pour obtenir $b'_{1 \dots n}$ et minimiser $f(b')$.

Entrée

La première ligne contient un entier unique $n$ ($1 \le n \le 16$). La seconde ligne contient $n$ entiers $a_{1 \dots n}$ ($|a_i| \le 10^5$).

Sortie

Affichez la valeur minimale possible de $f(b')$.

Exemples

Entrée 1

4
1 -1 1 1

Sortie 1

2

Entrée 2

6
4 -4 5 -20 6 7

Sortie 2

9