Nhặt hộp quà

Trên một băng chuyền có \(N\) hộp quà xếp thành hàng, đánh số từ \(1\) đến \(N\) theo thứ tự đi qua trước mặt bé Tom. Hộp quà thứ \(i\) chứa \(a_i\) viên kẹo.

Tom được phép nhặt một số hộp (có thể chỉ một hộp) theo đúng thứ tự chúng xuất hiện, với điều kiện hộp nhặt sau phải chứa số kẹo không ít hơn hộp nhặt ngay trước đó. Tom muốn tổng số kẹo nhặt được là lớn nhất.

Hãy cho biết tổng số kẹo lớn nhất mà Tom có thể mang về.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

In ra một số nguyên duy nhất: tổng số kẹo lớn nhất.

Constraints

• \(1 \le N \le 5000\)
• \(1 \le a_i \le 10^9\)

Sample Input 1

5
4 6 5 6 2

Sample Output 1

16

Sample Input 2

6
2 9 3 3 1 8

Sample Output 2

16

Explanation

Ở ví dụ 1, chọn các hộp có \(4, 6, 6\) kẹo (hộp 1, 2, 4) được \(16\) kẹo. Ở ví dụ 2, chọn các hộp \(2, 3, 3, 8\) (hộp 1, 3, 4, 6) được \(16\) kẹo.