# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# MSIS!

By moshiur_cse15 · Limits 1s, 256 MB

Do you know what MSIS is? MSIS is the abbreviation for Maximum Sum Increasing Subsequence. It is a subsequence of a given list of integers, whose sum is maximum and in the subsequence, all elements are sorted in strictly increasing order.

Given an array A of n positive integers. Write a program to find the sum of the elements of the MSIS.

N.B: A sub -sequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

## Input

First line of the input will contain an integer n, the number of elements in the array A. The second line will contain n space separated integers, the elements of the array A.
1 ≤ n ≤ 105
1 ≤ Ai ≤ 109

## Output

Print the sum of the elements of the MSIS of the given array A.

## Samples

InputOutput
```3
5 1 3
```
```5
```

All increasing subsequences have been listed below:
Sequence: , Sum: 5
Sequence: , Sum: 1
Sequence: , Sum: 3
Sequence: [1, 3], Sum: 4
Maximum sum is 5. So, the sum of the elements of the MSIS is 5.

InputOutput
```5
8 54 17 58 45
```
```120
```

Discussion
Statistics

64% Solution Ratio

tmwilliamlin168Earliest, 2w ago

NirjhorFastest, 0.1s

Tashdid_trdbLightest, 1.8 MB

tmwilliamlin168Shortest, 611B

Submit