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

Dữ liệu

Vào từ file văn bản MAXS.INP:

• 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~.

Kết quả

Ghi vào file văn bản MAXS.OUT một số nguyên là tổng lớn nhất tìm được.

Ràng buộc

• 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.

Example

Input

6
2 -3 8 4 -5 3

Output

12

Giải thích

~A_3 + A_4 = 8 + 4 = 12~.