Một hệ thống học trực tuyến cung cấp sẵn một danh sách gồm ~n~ bài luyện tập. Mỗi bài có một mức độ khó (tương ứng với một số nguyên dương). Các bài được sắp xếp theo thứ tự thời gian mà học sinh có thể truy cập.

Một học sinh muốn lập kế hoạch luyện tập bằng cách chọn ra một số bài trong danh sách để thực hiện, sao cho:

• Các bài được chọn phải giữ nguyên thứ tự xuất hiện trong danh sách (nghĩa là nếu chọn bài ở vị trí ~i~, thì chỉ được chọn tiếp các bài ở vị trí ~j > i~).
• Độ khó của các bài được chọn phải tăng dần, nghĩa là mỗi bài tiếp theo có độ khó lớn hơn bài trước đó (không được bằng hoặc giảm).
• Tổng độ khó của các bài được chọn là lớn nhất có thể.

Hãy giúp học sinh đó tính ra tổng độ khó lớn nhất mà bạn ấy có thể tích lũy được theo yêu cầu trên.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~), là số bài luyện có trong hệ thống.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~), là độ khó của các bài luyện, theo đúng thứ tự gợi ý trong hệ thống.

Dữ liệu ra

Ghi một số nguyên là tổng độ khó lớn nhất mà học sinh có thể đạt được nếu chọn một dãy bài luyện có độ khó tăng dần, giữ đúng thứ tự.

Ví dụ

Đầu vào 1

6                         
1 1 1 2 3 10

Đầu ra 1

16

Đầu vào 2

6                         
1 1 10 2 3 11

Đầu ra 2

22

Giải thích

• Với test ví dụ thứ nhất: Chọn các bài ở vị trí: ~1 → 4 → 5 → 6~, tương ứng độ khó ~1 → 2 → 3 → 10~, tổng lớn nhất là ~16~.
• Với test ví dụ thứ hai: Chọn các bài ở vị trí: ~1 → 3 → 6~, tương ứng độ khó ~1 → 10 → 11~, tổng lớn nhất là ~22~.

Tính điểm

• Subtask 1 ~(50\%)~: ~1 \leq n \leq 1000~.
• Subtask 2 ~(30\%)~: ~1 \leq n, a_i \leq 10^5~.
• Subtask 3 ~(20\%)~: Không có ràng buộc gì thêm.