Asteroid Collision

Asteroids move along a line. Each number is one asteroid: its absolute value is its size and its sign is its direction (positive moves right, negative moves left). All move at the same speed.

When two asteroids meet, the smaller one explodes; if they have the same size, both explode. Asteroids moving in the same direction never meet. Return the asteroids left after all collisions, in their original order.

For [5, 10, -5] the answer is [5, 10].

Examples

Example 1

Input:

asteroid_collision([5, 10, -5])

Output:

[5, 10]

Example 2

Input:

asteroid_collision([8, -8])

Output:

[]

Constraints

• 0 <= len(asteroids) <= 200000
• -1000 <= asteroids[i] <= 1000, asteroids[i] != 0