Given an array of n positive integers. Write the program to find the maximum sum subsequence of the given array such that the elements in subsequence in are in strictly decreasing order.

Note that strictly decreasing subsequence means that the next element in a particular subsequence must be smaller than the current element i.e. a_i > a_i+1 for all i such that 1<i<n.

Input

The first line contains an integer N denoting the number of elements in the array.

The second line contains N integers, the elements of the array.

Output

Print the maximum sum of elements formed by the decreasing subsequence of the array.

Constraints

1 < N < 101

1 < A[i] <100001