Description

Notwithstanding, today you're playing the game not of love but of cards. There is a deck with \(n\) cards each of which has a non-negative integer written on in front of you. From the top of the deck, you could perform the following actions sequentially:

• If the integer is positive, then you could either put the card on the top of your own pile, or discard it.
• Otherwise the integer is zero, you could remove the card from the top of your own pile and obtain the score of amount the integer written on, if your pile is not empty.

Initially, your pile is empty. As Freddie sang, "It’s so easy when you know the rules / It’s so easy, all you have to do / ...", you know all the integers written on every card beforehand. Therefore, you're crurious about what the maximum score that you could obtain is.

Input

The first the would be an integer \(n\).

And then, there would be \(n\) integers \(s_i\) in the following line, representing the integers written on the cards from top to bottom.

For 50% of the testcases,  \(n\leq5000\). As for the rest of the testcases, \(n\leq10^5\). It's guranteed that all integers written on the cards are non-negative and less than \(2^{31}\);

Output

Please print out a single integer that is the maximum score you could obtain. Beware of possible overflow!

Sample Input  Download

Sample Output  Download

Tags

Discuss