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 get $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 $f(b')$.