Cho mảng \(A\) gồm \(n\) phần tử. Hãy chọn ra ba 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 sáu chỉ số \(1 \le l \le r \lt i \le j \lt p \le k \le n\) sao cho \((A_l + ... A_r)\) + \((A_i + ... A_j)\) + \((A_p + ... A_k)\) lớn nhất.

Dữ liệu đầ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

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

Input 1

5
3 -2 8 -1 2

Output 1

13