Cho dãy số nguyên gồm N phần tử. Hãy tìm tổng lớn nhất của một đoạn con liên tiếp trong dãy.

• Input:
  • Dòng 1: số nguyên ~N (1 ≤ N ≤ 10^5)~.
  • Dòng 2: N số nguyên ~a[i] (|a[i]| ≤ 10^4)~.
• Output:
  • Một số nguyên: tổng lớn nhất của một đoạn con.

Ví dụ

Input 1

5
1 -2 3 4 -1

Output 1

7

Đoạn con có tổng lớn nhất là 3 4.

Input 2

4
-5 -2 -3 -4

Output 2

-2