MSIS!

moshiur_cse15 Ada Lovelace National Gir...
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 AA of nn positive integers. Write a program to find the sum of the elements of the MSIS.

N.B: A subsequence 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 nn (1n1051 ≤ n ≤ 10^5), the number of elements in the array AA (1Ai1091 ≤ A_i ≤ 10^9). The second line will contain nn space separated integers, the elements of the array AA.

Output

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

Samples

InputOutput
3
5 1 3
5

All increasing subsequences have been listed below:

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

Submit

Login to submit.

Contributors

Statistics

61% Solution Ratio
tmwilliamlin168Earliest, Jan '20
steinumFastest, 0.0s
steinumLightest, 8.6 kB
omar24Shortest, 571B
Toph uses cookies. By continuing you agree to our Cookie Policy.