Longest Increasing Subsequence with Maximum Sum

Given an array of n integers, you are asked to find the longest increasing subsequence of the array. If there are multiple such subsequences you can output any of them.

A subsequence of an array is obtained by deleting some (possibly zero) elements of the array, without changing the order of the remaining elements. For example, if the array is , then is a subsequence of , but is not a subsequence of , since the order of the elements is not preserved.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000), the length of the array.

The second line contains n space-separated integers (), representing the elements of the array.

Output

The program should print the sum of the longest increasing subsequence with the maximum sum.

Explanation

1. In the first example, the longest increasing subsequence with maximum sum is .

2. In the second example, the longest increasing subsequence with maximum sum is .