Maximum Sum Increasing Subsequence#11653

Maximum Sum Increasing Subsequence

1 second
128 megabytes
Medium

Given a sequence a_1, a_2, \ldots, a_n of length . Find its subsequence a_{i_1}, a_{i_2}, \ldots, a_{i_k} such that

Input

The first line contains the size of array (n \le 10^4). The second line contains integers a_i (0 \le a_i \le 10^5).

Output

Print the sum of the maximum sum subsequence.

Examples

For example, if input is \{3, 2, 100, 4, 5, 6\}, then output should be 103 = 3 + 100.

Example 1

Loading
Loading