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 các thí sinh Free Contest:

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~.

Input

• 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~.

Output

• 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.

Sample

Input #1

5
-3 5 -10 8 -2

Output #1

26

Problem source: Kc97ble - Free Contest 40