Biểu thức ngoặc đúng được định nghĩa như sau:

• Một xâu rỗng biểu diễn một biểu thức ngoặc đúng.
• Nếu \(A\) là một xâu biểu diễn một biểu thức ngoặc đúng thì \((A)\) cũng là biểu diễn một biểu thức ngoặc đúng.
• Nếu hai xâu \(A, B\) là xâu biểu diễn biểu thức ngoặc đúng thì \(AB\) cũng là biểu diễn một biểu thức ngoặc đúng.

Thầy Alice muốn tạo một biểu thức ngoặc đúng, có \(n\) vị trí có thể đặt ngoặc. Các vị trị được đánh số từ \(1\) đến \(n\) từ trái sang phải, bắt đầu với giá trị \(s = 0\), tại mỗi vị trí \(i\) \((1 \leq i \leq n)\) thầy Alice có ba lựa chọn:

• Đặt ví trí này là dấu ( và thay \(s = s + a_{i}\).
• Đặt ví trí này là dấu ) và thay \(s = s - a_{i}\).
• Bỏ qua vị trí này.

Sau khi lựa chọn xong, lấy các kí tự từ trái sang phải ở các vị trí đặt dấu ( hoặc ) để tạo được biểu thức ngoặc đúng mà \(s\) đạt giá trị lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\)

Output

• Ghi ra một số nguyên duy nhất là giá trị \(s\) lớn nhất có thể chọn được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(25\%\) số điểm): không có quá \(10^{3}\) giá trị \(a_{i}\) khác \(0\).
• Subtask \(4\) (\(25\%\) số điểm): không có rằng buộc gì thêm.

Example

4
0 -5 1 2

5

9
5 -2 2 3 -4 -4 -1 -2 9

21