Tổng liên tiếp

Cho một dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Yêu cầu: Hãy tìm đ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}, \dots, A_{r-1}, A_r\) của dãy \(A\) sao cho tổng \(A_l + A_{l+1} + \dots + A_{r-1} + A_r\) là lớn nhất

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^5\) và \(|A_i|\le 10^9\).

Output

Một số nguyên là tổng lớn nhất tìm được.

Example

6
2 -3 8 4 -5 3

12

Scoring

• Subtask 1: \(20\%\) số test ứng với \(1 \le N \le 100\)
• Subtask 2: \(20\%\) số test ứng với \(1 \le N \le 10^4\)
• Subtask 3: \(20\%\) số test ứng với \(A_i \ge 0\).
• Subtask 4: \(40\%\) số test không có ràng buộc gì thêm.