Hộp quà cỡ lớn

Một dãy \(N\) hộp quà được xếp thành hàng ngang, đánh số từ \(1\) đến \(N\). Hộp thứ \(i\) đựng \(a_i\) viên kẹo.

Bạn được chọn ra một số hộp (ít nhất một hộp), giữ nguyên thứ tự ban đầu, sao cho số kẹo trong các hộp được chọn không giảm từ trái sang phải. Trong mọi cách chọn hợp lệ, hãy tìm tổng số kẹo lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, \dots, a_N\), cách nhau bởi dấu cách.

Output

In ra một số nguyên là tổng số kẹo lớn nhất có thể đạt được.

Constraints

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

Sample Input 1

5
7 7 2 9 3

Sample Output 1

23

Sample Input 2

4
5 4 3 2

Sample Output 2

5

Explanation

Ví dụ 1: chọn \(7, 7, 9\) được \(23\). Ví dụ 2: dãy giảm dần nên chỉ chọn được một hộp, tốt nhất là hộp \(5\) kẹo.