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

제한

힌트