Para una secuencia $a_{1 \dots n}$, definimos $f(a)$ como:
$$f(a) = \max_{1 \le l \le r \le n} \sum_{i=l}^{r} a_i$$
Dada una secuencia $b_{1 \dots n}$, usted debe permutar $b_{1 \dots n}$ para obtener $b'_{1 \dots n}$ y minimizar $f(b')$.
Entrada
La primera línea contiene un único entero $n$ ($1 \le n \le 16$).
La segunda línea contiene $n$ enteros $a_{1 \dots n}$ ($|a_i| \le 10^5$).
Salida
Imprima el valor mínimo posible de $f(b')$.
Ejemplos
Entrada 1
4 1 -1 1 1
Salida 1
2
Entrada 2
6 4 -4 5 -20 6 7
Salida 2
9