시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 6 3 3 75.000%

문제

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

예제 입력 1

4
1 -1 1 1

예제 출력 1

2

예제 입력 2

6
4 -4 5 -20 6 7

예제 출력 2

9