Ai cũng biết về truyền thuyết ông già Noel với những món quà diệu kỳ, nhưng ít ai biết rằng chính Nhật Tăng, người được giao nhiệm vụ phân chia quà tặng, lại phải đối mặt với thử thách riêng của mình. Trước mắt anh là một dãy gồm ~N~ món quà, được sắp xếp theo thứ tự từ ~1~ đến ~N~ với giá trị tương ứng là ~A_1, A_2, …, A_N~. Công việc của anh là chọn ra một số món quà theo đúng thứ tự ban đầu sao cho giá trị của mỗi món quà được chọn tăng dần từ trái qua phải, nghĩa là món quà đứng trước luôn có giá trị nhỏ hơn món quà đứng sau. Mục tiêu cuối cùng là sao cho tổng giá trị của các món quà được chọn là lớn nhất, để đảm bảo các em nhỏ nhận được những phần quà giá trị nhất từ ông già Noel. Bạn hãy giúp Nhật Tăng thực hiện công việc này và tính ra tổng giá trị lớn nhất có thể đạt được.

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(N \leq 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên không âm ~A_1, A_2, …, A_N~ (mỗi số không vượt quá ~10^6~).

Output

• In ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà được chọn.

Sample Input

7
1 4 5 2 4 3 4

Sample Output

10

Note

• Trong trường hợp này, các món quà được chọn có thể là món thứ ~1~, thứ ~2~ và thứ ~7~ với giá trị tương ứng là ~1, 4, 5~; tổng giá trị là ~1 + 4 + 5 = 10~.