Maximum-Sum Increasing Subsequence 2

Problem Description

You are given an array $a_1,a_2,\dots ,a_n$ of length $n$. Find the increasing subsequence with the maximum sum. That is, find indices $p_1,p_2,\dots,p_m$ satisfying $1\leq p_1 < p_2 < \dots < p_m \leq n$ and $a_{p_1} < a_{p_2} < \dots < a_{p_m}$, so as to maximize $a_{p_1} + a_{p_2} + \dots + a_{p_m}$.

Input Format

The first line contains one number $n$.

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

Output Format

Output one number, the answer.

Sample Input

6
3 7 4 2 6 8

Sample Output

21

Constraints

For all data, $1\leq n\leq 2 \times 10^5$ and $1 \leq a_i \leq 2\times 10^5$ are guaranteed.