Cho dãy ~n~ số nguyên ~a_1, a_2, ..., a_{n-1}, a_n~. Với mỗi đoạn từ ~a_i~ đến ~a_j~ (~1 \le i < j \le n~) của dãy đã cho, tổng ~T = a_i - a_{i+1} + a_{i+2} - ... a_j~ gọi là tổng đan dấu của đoạn ~[i, j]~, ví dụ: đoạn ~[2, 2]~ có ~T = a_2~; đoạn ~[3, 7]~ có ~T = a_3 - a_4 + a_5 - a_6 + a_7~.

Yêu cầu: Tìm đoạn có tổng đan dấu lớn nhất.

INPUT

Dòng đầu tiên ghi số nguyên dương ~n~ (~3 \le n \le 10^6~).

Dòng thứ hai ghi lần lượt các số ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~)

OUTPUT

Ghi tổng đan dấu lớn nhất tìm được

SAMPLE INPUT

4
2 4 3 5

SAMPLE OUTPUT

6

SUBTASKS