Cho mảng ~A~ gồm ~N~ phần tử. Tìm dãy con gồm các phần tử liên tiếp ~S~ của dãy ~A~ sao cho tổng tất cả các phần tử của ~S~ là lớn nhất và in ra tổng đó.

Input

• Dòng đầu, chứa số nguyên dương ~N~ ~(1 ≤ N ≤ 1000)~;
• Dòng tiếp theo gồm ~N~ số nguyên ~A_i~ ~(−10^9 ≤ A_i ≤ 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample

Input #1

3
1 -3 3

Output #1

3

Problem source: Kc97ble - Free Contest