Cho dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\).
Gọi \(S(L, R)\) là tổng các phần tử thuộc dãy con từ chỉ số \(L\) đến \(R - 1\).

Ví dụ: Với \(A = (3, -4, 1, 6)\) thì:

• \(S(1,2) = 3\)
• \(S(1,3) = -1\)
• \(S(1,5) = 6\)

Yêu cầu

Hãy tìm 3 chỉ số \(p_1, p_2, p_3\) \((1 \le p_1 \le p_2 \le p_3 \le N+1)\) để chia dãy \(A\) thành các dãy con sao cho \(S(1, p_1) - S(p_1, p_2) + S(p_2, p_3) - S(p_3, N+1)\) đạt giá trị lớn nhất có thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\).

Kết quả

In ra một số nguyên duy nhất là giá trị lớn nhất có thể của \(S(1, p_1) - S(p_1, p_2) + S(p_2, p_3) - S(p_3, N+1)\)

Subtask

Trong tất cả các test, với mọi \(i\): \(|A_i| \le 10^9\).

• Subtask 1 (50%): \(N \le 2 \times 10^2\)
• Subtask 2 (25%): \(N \le 2 \times 10^3\)
• Subtask 3 (25%): \(N \le 2 \times 10^5\)

Ví dụ

Input

5
2 8 -1 7 -2

Output

20