Cho một dãy số gồm \(n\) số nguyên dương \(a_1,a_2,… ,a_n\) . Xét các dãy con là dãy các phần tử liên tiếp nhau của dãy ban đầu, mà trong đó các phần tử là không giảm \((a_i ≤ a_{i+1} ≤ … ≤ a_{j-1} ≤ a_j; 1 ≤ i ≤ j ≤ n).\)

Yêu cầu: Tìm các dãy con có tổng các phần tử là lớn nhất trong các dãy con không giảm trên.

Dữ liệu: File SUBSEQ15.INP có cấu trúc như sau:

• Dòng đầu tiên ghi số nguyên dương \(n( 1≤n≤10^6 ).\)

• Dòng tiếp theo ghi \(n\) số nguyên dương \(a_1,a_2,…,a_n (1≤a_i≤10^6 ).\)

Kết quả: File SUBSEQ15.OUT có cấu trúc như sau:

• Gồm một dòng ghi tổng lớn nhất tìm được.

Ràng buộc:

• Có 20% số điểm ứng với: \(n≤10\) và dãy ban đầu là một dãy không giảm;

• Có 20% số điểm ứng với \(11≤n ≤ 200;\)

• Có 20% số điểm ứng với \(201≤n ≤ 10^3;\)

• 40% số điểm còn lại không có ràng buộc gì thêm.

Sample INput

10
2 2 3 4 6 6 7 7 8 8

Sample Output

53

Sample Input

11
4 7 4 5 7 4 9 3 3 4 6

Sample Output

16