Max Special Subsequence Sum

You are given an integer n and a sequence of n integers. A special subsequence is defined as a strictly increasing subsequence. Your task is to find the maximum possible sum of such a subsequence.

Formally, given a sequence \(a_1, a_2, \dots, a_n\), you need to choose a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) (with \(1 \le i_1 < i_2 < \dots < i_k \le n\)) such that \[ S = \sum_{j=1}^{k} a_{i_j} \] is maximized under the condition that \[ a_{i_1} < a_{i_2} < \dots < a_{i_k}. \]

If n = 0 (i.e. the sequence is empty), output 0. Note that the sequence can contain negative numbers.

inputFormat

The first line contains an integer n, the number of elements in the sequence.

The second line contains n space-separated integers representing the sequence. If n = 0, the second line will be empty.

outputFormat

Output a single integer, which is the maximum sum of a strictly increasing subsequence of the given sequence.

5
1 101 2 3 100

106