Dla ciągu $a_{1 \dots n}$ definiujemy $f(a)$ jako:

$$f(a) = \max_{1 \le l \le r \le n} \sum_{i=l}^{r} a_i$$

Mając dany ciąg $b_{1 \dots n}$, należy wyznaczyć taką permutację $b'_{1 \dots n}$ ciągu $b_{1 \dots n}$, aby zminimalizować $f(b')$.

Wejście

W pierwszej linii znajduje się pojedyncza liczba całkowita $n$ ($1 \le n \le 16$). W drugiej linii znajduje się $n$ liczb całkowitych $a_{1 \dots n}$ ($|a_i| \le 10^5$).

Wyjście

Wypisz minimalną możliwą wartość $f(b')$.

Przykład

Wejście 1

4
1 -1 1 1

Wyjście 1

2

Wejście 2

6
4 -4 5 -20 6 7

Wyjście 2

9