Record fraud (find an algorithm)

Difficulty: Beginner

You work in a start up with very unstable finances. You have a chronological list of all income (positive integers) and expenses (negative integers), and you need to share it with investors.

However, you don't want the busines to appear unprofitable. In fact, you want it to seem as if the busines has never been in the red ever. You do this by selectively removing expenses from the list, removing as few as possible to avoid rasing suspicion.

What does the list given to the investors look like?

Input

An array of integers history

Output

An array of integers cleared where

• cleared is a subsequece of hisory
• sum(cleared[:n]) is non-negative for all n
• len(cleared) is maximized

If multiple outputs fulfill the requirements, return any one of them

Constraints

len(history) <= 100 000

abs(history[i]) <= 10^9

Example

Input

[-3, 8, -4, -5, 4, -2, -3, -2, -2, 5, -6, 2, -5, -5]

Possible output

[8, 4, -2, -3, -2, -2, 5, 2, -5, -5]

Try to make an algorithm that's O(n log n)