Maximum Sum Increasing Subsequence

Given an array of integers, your task is to find a subsequence that is strictly increasing and has the maximum possible sum. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Let \(dp[i]\) denote the maximum sum of an increasing subsequence ending at index \(i\). Then, the recurrence relation can be written as follows:

\[ dp[i] = arr[i] + \max_{0 \leq j < i \text{ and } arr[j] < arr[i]} (dp[j]) \]

If no valid \(j\) exists, then \(dp[i] = arr[i]\). The answer is \(\max(dp[i])\) for \(0 \leq i < n\), where \(n\) is the number of elements in the array.

If the array is empty, output 0.

inputFormat

The first line contains a single integer \(n\) (\(0 \leq n \leq 10^5\)) representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single integer, the maximum sum of a strictly increasing subsequence of the array.

## sample

6
10 20 30 5 10 50

110