21103번 - 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')$.