# 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

InputOutput
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.

InputOutput
5
8 54 17 58 45

120