Maximum Sum Increasing Subsequence

Given a sequence $a_1,a_2,...,a_n$ of length $n$. Find its subsequence $a_{i_1},a_{i_2},...,a_{i_k}$ such that

• the numbers in the subsequence are sorted in strictly ascending order.

• the sum of numbers in the subsequence $a_{i_1}+a_{i_2}+...+a_{i_k}$ is the biggest

Input

The first line contains the size of array $n(n\le 10^4)$.The second line contains $n$ integers $a_i(0\le a_i\le 10^5)$.

Output

Print the sum of the maximum sum subsequence.

Examples

For example, if input is $\{3,2,100,4,5,6\}$, then output should be $103(3+100)$.