Для последовательности $a_{1 \dots n}$ определим $f(a)$ как:

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

Дана последовательность $b_{1 \dots n}$. Вам необходимо переставить элементы $b_{1 \dots n}$, чтобы получить $b'_{1 \dots n}$ и минимизировать $f(b')$.

Входные данные

Первая строка содержит единственное целое число $n$ ($1 \le n \le 16$). Вторая строка содержит $n$ целых чисел $b_{1 \dots n}$ ($|b_i| \le 10^5$).

Выходные данные

Выведите минимально возможное значение $f(b')$.

Примеры

Входные данные 1

4
1 -1 1 1

Выходные данные 1

2

Входные данные 2

6
4 -4 5 -20 6 7

Выходные данные 2

9