Với một dãy $b_{1 \dots n}$, ta định nghĩa $f(b)$ là:

$$f(b) = \max_{1 \le l \le r \le n} \sum_{i=l}^r b_i$$

Cho một dãy $b_{1 \dots n}$, bạn cần hoán vị $b_{1 \dots n}$ để nhận được $b'_{1 \dots n}$ sao cho $f(b')$ đạt giá trị nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 16$). Dòng thứ hai chứa $n$ số nguyên $b_{1 \dots n}$ ($|b_i| \le 10^5$).

Dữ liệu ra

In ra giá trị nhỏ nhất có thể của $f(b')$.

Ví dụ

Dữ liệu vào 1

4
1 -1 1 1

Dữ liệu ra 1

2

Dữ liệu vào 2

6
4 -4 5 -20 6 7

Dữ liệu ra 2

9