Maximum Sum Increasing Subsequence

Problem Description

Given an array $a_1, a_2, \dots, a_n$ of length $n$, find the increasing subsequence with the largest sum. That is, find indices $p_1, p_2, \dots, p_m$ satisfying $1\le p_1 < p_2 < \dots < p_m \le n$ and $a_{p_1} < a_{p_2} < \dots < a_{p_m}$, such that $a_{p_1} + a_{p_2} + \dots + a_{p_m}$ is maximized.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

One number: the answer.

Sample Input

6
3 7 4 2 6 8

Sample Output

21

Constraints

For all data, $1\le n\le 1000, 1 \le a_i \le 10^5$.