Hero's Quest: The Magical Creatures

A young hero embarks on his first quest. A wise wizard provides him with a clue in the form of a list of \( n \) integers \( a_{i} \). The hero meets \( n \) magical creatures in a specific order. Depending on the value of \( a_{i} \), each creature behaves differently:

• If \( a_{i} > 0 \), the creature is benevolent and gives the hero a magical item of type \( a_{i} \). The hero can have several items of the same type.
• If \( a_{i} < 0 \), the creature is evil. To defeat this creature, the hero must use one magical item of type \( -a_{i} \). Note that magical items are fragile and can be used only once.
• If \( a_{i} = 0 \), the creature is a unicorn. It grants the hero exactly one magical item of his choice (i.e. the hero can choose any type he needs).

The hero must face the creatures one by one in the given order. Determine whether it is possible for the hero to complete the quest by defeating all evil creatures. The hero starts with no items. When encountering a benevolent creature, he collects the given item. When meeting a unicorn, he can delay choosing the type until it is needed later for an enemy, but he can use each unicorn gift only once. If at any point an evil creature requires an item that is unavailable from previous benevolent gifts or unassigned unicorn gifts, the quest fails.

Your task is to decide whether the hero can defeat all the enemies in the given sequence.

inputFormat

The first line contains an integer \( n \) (the number of magical creatures). The second line contains \( n \) space-separated integers \( a_{1}, a_{2}, \dots, a_{n} \) representing the clue given by the wizard.

outputFormat

Print YES if it is possible for the hero to defeat all the enemies; otherwise, print NO.

sample

5
1 -1 0 -1 1

YES