n pieces of space debris travel along a single straight line, given in left-to-right position order. Each piece is described by one nonzero integer: its sign gives the direction of travel (positive = moving right/east, negative = moving left/west), and its absolute value gives its size. All pieces move at the same speed.
Two pieces collide only when a right-moving piece is immediately followed (considering only pieces that are still alive) by a left-moving piece — since same-direction pieces never catch up to each other, and a left-moving piece can never catch up to a right-moving piece ahead of it. When a collision happens: the piece with the strictly larger size survives unchanged and destroys the other; if both pieces have equal size, both are destroyed. A surviving right-moving piece may go on to collide with the next surviving left-moving piece after it, and so on.
After all collisions have finished, report the sizes and directions (as signed integers, in their original relative order) of every piece that survives.
Input format
Line 1: an integer n.
Line 2: n space-separated nonzero integers, the signed sizes in left-to-right order.
Output format
The surviving signed sizes, space-separated, in their original left-to-right order, on one line (an empty line if nothing survives).
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ absolute value of each piece ≤ 1000000000