Câu 3: Tổng liên tiếp (5.0 điểm)

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

Đọc từ file MAXS.INP gồm:

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \le 10^5)\) là số phần tử trong dãy;
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((|a_i| \le 10^9, 1 \le i \le N)\).

Output

Ghi ra file MAXS.OUT 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

• 20% số test: \(N \le 100\)
• 20% số test: \(N \le 10^4\)
• 20% số test: \(N \le 10^5\) và \(a_i \ge 0\) \((1 \le i \le N)\)
• 40% số test: \(N \le 10^5\)