Nhị vừa học về tổng tiền tố, và thầy giáo của anh cho anh bài toán sau:

Cho dãy số A gồm n số nguyên ~a_1, a_2, ..., a_n~.

1. Gọi ~f(i, j)~ = |~a_i~| + |~a_{i+1}~| + ... + |~a_j~ |. Tìm giá trị lớn nhất của ~f(i, j)~ với ~1 ≤ i ≤ j ≤ n~.

2. Gọi ~g(i, j)~ = ~a_i~ + ~a_{i+1}~ + ... + ~a_j~ . Tìm giá trị lớn nhất của ~g(i, j)~ với ~1 ≤ i ≤ j ≤ n~.

Sau khi giải xong hai bài toán trên một cách dễ dàng, Nhị nhận thấy hai hàm ~f(i, j)~ và ~g(i, j)~ không có liên quan gì đến nhau, vì vậy anh đề xuất một bài toán hại não hơn:

Cho dãy số A gồm n số nguyên ~a_1, a_2, ..., a_n~. Tìm giá trị lớn nhất của ~f(i, j) + g(i, j)~ với ~1 ≤ i ≤ j ≤ n~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 ≤ n ≤ 5 × 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| ≤ 10^9)~

Kết quả

• Gồm một dòng chứa một số nguyên dương duy nhất là kết quả của bài toán.

Ví dụ

Sample Input

5

-3 5 -10 8 -2

Sample Output

26