Đoạn con có tổng lớn nhất

Cho một dãy \(A\) gồm \(N\) số nguyên \(a_1, a_2, \ldots, a_N\). Đoạn con \([l, r]\) (\(1 \le l \le r \le N\)) gồm các phần tử liên tiếp \(a_l, a_{l+1}, \ldots, a_{r-1}, a_r\) của dãy \(A\) có tổng \(S = a_l + a_{l+1} + \cdots + a_{r-1} + a_r\). Hãy tìm giá trị lớn nhất của \(S\).

Input

Dữ liệu vào gồm:

• Dòng đầu tiên chứa số nguyên dương \(N\) là số phần tử trong dãy;

• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(|a_i| \le 10^9\), \(1 \le i \le N\)).

Ràng buộc:

• Có \(15\%\) số điểm của bài có \(N \le 100\);

• Có \(35\%\) số điểm của bài có \(N \le 10\,000\);

• Có \(10\%\) số điểm của bài có \(N \le 100\,000\) và \(a_i \ge 0\) với mọi \(i = 1 \ldots N\);

• Có \(40\%\) số điểm của bài có \(N \le 100\,000\).

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của \(S\).

Example

Input:

6
-2 7 -8 4 6 -1

Output:

10

Note

Chọn đoạn con \([4, 5]\) gồm hai phần tử \(4\) và \(6\) có tổng \(4 + 6 = 10\). Đây là tổng lớn nhất trong tất cả các đoạn con (đoạn \([2, 5]\) chỉ có tổng \(7 - 8 + 4 + 6 = 9\)).