Solve the programming task below in a Python markdown code block.
problem

Given the sequence $ A $ of length $ N $. Find the maximum value of $ \ sum B_i $, where $ B $ is one of the longest increasing subsequences of the sequence $ A $.

The longest increasing subsequence of the sequence $ A $ is the longest subsequence that satisfies $ A_i <A_j $ with all $ i <j $.



output

Output the maximum value of $ \ sum B_i $, where $ B $ is one of the longest increasing subsequences of the sequence $ A $. Also, output a line break at the end.

Example

Input

4
6 4 7 8


Output

21