MSIS!

Limits 1s, 256 MB

Do you know what MSIS is? MSIS is the abbreviation for Maximum Sum Increasing Subsequence. It is a subsequence of a given list of integers, whose sum is maximum and in the subsequence, all elements are sorted in strictly increasing order.

Given an array $A$ of $n$ positive integers. Write a program to find the sum of the elements of the MSIS.

N.B: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input

First line of the input will contain an integer $n$ ( $1 ≤ n ≤ 10^5$ ), the number of elements in the array $A$ ( $1 ≤ A_i ≤ 10^9$ ). The second line will contain $n$ space separated integers, the elements of the array $A$ .

Output

Print the sum of the elements of the MSIS of the given array $A$ .

Samples

Input	Output
3 5 1 3	5
All increasing subsequences have been listed below: Sequence: $[5]$ , Sum: 5 Sequence: $[1]$ , Sum: 1 Sequence: $[3]$ , Sum: 3 Sequence: $[1, 3]$ , Sum: 4 Maximum sum is 5. So, the sum of the elements of the MSIS is 5.

Input

Output

3
5 1 3

All increasing subsequences have been listed below:

Sequence: $[5]$ , Sum: 5
Sequence: $[1]$ , Sum: 1
Sequence: $[3]$ , Sum: 3
Sequence: $[1, 3]$ , Sum: 4

Maximum sum is 5. So, the sum of the elements of the MSIS is 5.

Input	Output
5 8 54 17 58 45	120