Cho dãy ~n~ số nguyên ~a_1,a_2,\ldots,a_n~. Với mỗi đoạn ~[i,j]~, tổng đan dấu của đoạn là ~a_i-a_{i+1}+a_{i+2}-\cdots~ cho đến ~a_j~.

Yêu cầu

Tìm tổng đan dấu lớn nhất của một đoạn con liên tiếp.

Input

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

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(|a_i| \le 10^9)~.

Output

In ra tổng đan dấu lớn nhất.

Subtask

• Có 50% số test có ~3 \le n \le 10^2~.
• Có 30% số test có ~10^2 < n \le 5\cdot 10^3~.
• Có 20% số test còn lại không có ràng buộc bổ sung.

Ví dụ

4
2 4 3 5

6