Cho một mảng gồm ~N~ số nguyên, hãy tìm độ dài lớn nhất của một dãy con tăng (không nhất thiết liên tiếp) trong mảng.

Một dãy con tăng là dãy thỏa mãn:

• Chọn ra một số phần tử theo đúng thứ tự xuất hiện trong mảng (không cần liên tiếp),
• Mỗi phần tử sau lớn hơn phần tử đứng trước nó.

Nhiệm vụ của bạn là tìm ra dãy con tăng có tổng nhất

Dữ liệu

Gồm ~2~ dòng:

• Dòng đầu chứa số nguyên ~N~ ~(1 \le N \le 1000)~
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ ~(a_i \le 10^9)~

Kết quả

In ra giá trị dãy con tăng có tổng lớn nhất.

Ví dụ

Sample Input

5
2 1 4 3 5

Sample Output

11

Giải thích: Một dãy con tăng có thể là: 2 → 4 → 5

Subtask

• ~30\%~ số test có ~a_i = i~
• ~30\%~ số test tiếp theo có ~N \le 10~
• ~40\%~ số test còn lại có ~N \le 1000~