Cho một mảng ~N~ phần tử, hỏi mảng con liên tục không rỗng có tổng lớn nhất là bao nhiêu

Input

• Dòng đầu tiên có số nguyên ~N~ ~(1 \leq N \leq 10^5)~ đại diện cho chiều dài mảng.
• Dòng tiếp theo gồm ~N~ số nguyên ~a_i~ ~(-10^6 \leq a_i \leq 10^6)~ đại diện cho giá trị của phần tử thứ ~i~

Output

• Một số nguyên duy nhất là tổng lớn nhất được tạo từ một mảng con liên tiếp không rỗng.

Sample Input 1

5
7 -2 -3 8 -1

Sample Output 1

10

Sample Input 2

5
4 -2 -3 8 -1

Sample Output 2

8