题目描述
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
输入格式
见题面
输出格式
见题面
样例输入
4
6 4 7 8
样例输出
21