Cho dãy ~n~ số nguyên ~a_1,a_2,\ldots,a_n~. Hãy tìm tổng lớn nhất của một dãy con gồm các phần tử liên tiếp.

Input

Dòng đầu chứa số nguyên dương ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Output

In ra tổng lớn nhất tìm được.

Subtask

• 40% số điểm: ~n \le 500~.
• 40% số điểm: ~n \le 5000~.
• 20% số điểm: ~n \le 10^6~, ~|a_i| \le 10^3~.

Ví dụ

5
-5 2 -1 0 4

5