Cho mảng \(A\) gồm có \(n\) phần tử. Hãy chọn ra hai mảng con khác rỗng không giao nhau của \(A\) sao cho tổng của chúng là lớn nhất. Nói cách khác, chọn ra bốn chỉ số \(1 \le l \le r \lt i \le j \le n\) sao cho

\((A_l+A_{l+1}+...A_r) + (A_i+A_{i+1}+...A_j)\) lớn nhất.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\)
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Dữ liệu ra

• In ra một số nguyên là tổng lớn nhất.

Điều kiện

• \(1 \le n \le 10^5\)
• \(0 \le |A_i| \le 10^9\)

Input 1

5
3 -2 8 -1 2

Output 1

12