Maximum Subsequence

For a sequence $a_{1...n}$, define $f(a)$ as

$f(a) = \max\limits_{1 \le l \le r \le n} \sum\limits_{i = l}^{r} a_i\text{.}$

Given a sequence $b_{1...n}$, you need to permute $b_{1...n}$ to obtain $b'_{1...n}$ and minimize $f(b')$.

The first line contains a single integer $n$ ($1 \le n \le 16$).

The second line contains $n$ integers $a_{1...n}$ ($|a_i| \le 10^5$).

Output the minimum possible value of $f(b')$.