Cho dãy số nguyên \(A1, A2, A3,...AN\) (\(|A[i]| \le 1e12\))
Một đoạn con của dãy A là một tập hợp các số hạng liên tiếp \(A1, A2, A3,...AK\)(\(i = 1 -> N; K \le N\))
Chú ý mỗi phần tử của dãy \(A\) cũng được tính là 1 đoạn con của dãy \(A\)
Giờ với mỗi đoạn con hãy tính tổng và đưa ra tổng đoạn con lớn nhất tìm được

Thông số đầu vào

Dòng 1 chứa số nguyên \(N\) (\(N \le 10^6\))
Dòng 2 chứa \(N\) số \(A[i]\) (\(i = 1 -> N\))

Thông số đầu ra

Một số nguyên là giá trị tổng đoạn con lớn nhất tìm được

Ví dụ đầu vào

7
-2 3 4 -6 1 -9 7

Ví dụ đầu ra

7

Ràng buộc

Có 60% số test với \(N \le 10^4, |A[i]| \le 10^6\)
Có 20% số test với \(N \le 10^5, |A[i]| \le 10^9\)
20% số test còn lại không ràng buộc gì thêm