Cho một mảng gồm ~N~ số nguyên, nhiệm vụ của bạn là tìm dãy con liên tiếp có tổng lớn nhất. Chú ý rằng dãy được chọn phải có ít nhất ~1~ phần tử.

Dữ liệu

Gồm ~2~ dòng:

• Dòng đầu tiên chứa số nguyên ~N~ ~(N \leq 10^5)~.
• Dòng thứ 2 chứa ~N~ số nguyên ~a_i~ ~(\left| a_i \right| \leq 10^9)~ phân tách bằng dấu cách.

Chú ý: ~a_i~ có thể là số âm

Kết quả

In ra 1 số nguyên là tổng của dãy con thỏa mãn đề bài.

Sample Input

8
-1 3 -2 5 3 -5 2 2

Sample Output

9

Subtask

• ~30\%~ số test có ~N \le 100~
• ~30\%~ số test tiếp theo có ~N \le 3000~
• ~40\%~ số test còn lại không có điều kiện gì thêm