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: [5], Sum: 5
Sequence: [1], Sum: 1
Sequence: [3], 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

Login to submit