Robot 2

Có \(N\) viên gạch vuông bằng nhau xếp sát nhau thành một hàng dài. Trên viên gạch thứ \(i\) có ghi một giá trị \(A_i\).

Một Robot được đặt ở viên gạch thứ nhất. Robot sẽ nhảy dọc theo hàng gạch và phải kết thúc ở viên gạch cuối cùng (viên gạch thứ \(N\)).
Do hạn chế về kỹ thuật và năng lượng, bước nhảy tiếp theo của Robot không thể dài hơn bước nhảy ngay trước đó.
Cụ thể, nếu Robot đang ở viên gạch thứ \(i\) nhảy tới viên gạch thứ \(j\) (\(i<j\)), sau đó từ viên gạch thứ \(j\) nhảy tới viên gạch thứ \(k\) (\(j<k\)) thì

Yêu cầu: Hãy tìm tổng giá trị lớn nhất trên các viên gạch mà Robot nhảy tới (tính cả viên đầu và viên cuối).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((1\le N\le 10^3)\).
• Dòng thứ hai chứa \(N\) giá trị \(A_1,A_2,\ldots,A_N\) \((-10^9 \le A_i \le 10^9)\).

Output

In ra một số nguyên duy nhất là tổng giá trị lớn nhất trên các viên gạch mà Robot nhảy tới.

Giải thích: Một cách nhảy đạt tổng lớn nhất là \(1 \to 3 \to 5 \to 6\), tổng nhận được là
\(A_1 + A_3 + A_5 + A_6 = 1 + 5 + (-1) + 2 = 7\).

Scoring

• Subtask 1: \(1 \le N \le 20\).
• Subtask 2: \(20 \le N \le 500\).
• Subtask 3: Không có ràng buộc bổ sung.

Sample Input 1

6
1 -1 5 -2 -1 2

Sample Output 1

7