Tidal Waves

hard

NASA is studying an unnatural tidal wave phenomenon on a distant planet. They've recorded a sequence of incoming waves represented by an array w. Each wave has a direction and strength:

  • The absolute value of each number represents the wave's height in meters.
  • The sign indicates the direction: positive means flowing eastward, negative means flowing westward.
  • The index in the array represents the wave's position in the observation sequence.

When waves flowing in opposite directions meet, they create a collision. In a collision:

  • If one wave is taller than the other, the smaller wave dissipates completely while the taller wave continues its course.
  • If both waves are of equal height, they neutralize each other and both dissipate.
  • Waves flowing in the same direction never interact with each other.

Given the initial wave measurements, determine which waves will remain after all possible collisions have occurred.

Input Format:

The first line contains an integer nn (1≤n≤105)(1 \leq n \leq 10^5), representing the size of array ww. The second line contains nn integers w1,w2,…,wnw_1, w_2, \dots, w_n, representing the array ww. (−106≤wi≤106)(-10^6 \leq w_i \leq 10^6)

Output Format:

Give the output as a sequence of integers representing the direction and strength of remaining waves.

Examples:

Example 1:

Input:

3
5 10 -5

Output:

5 10

Example 2:

Input:

3
10 2 -5

Output:

10

Code

Loading Editor...