Given an array of integers ~A~. A subarray of array ~A~ is an array of zero or more consecutive elements in ~A~.

Given array ~A~, find the largest possible absolute sum of a non-empty subarray of ~A~.

Input

• The first line is an integer ~n~ (~n \leq 10^6~)
• The second line is the ~n~ integers of array ~A~ ~(A_i \le 10^9)~.

Output

• The largest possible sum

Example Input 1

7
-1 2 4 -1 6 -10 1

Example Output 1

11