Number Colosseum

Interview

Time limit1sMemory limit1024 MB

Summary

Each new contestant fights the most recent opposing contestant still inside, and the task asks which team wins and which integers remain, in arrival order.

Level: Medium4 of 10
Topics: Stack, Simulation
Solved: No attempts yet

Problem

Welcome to the Number Colosseum, where two teams of integers are preparing to battle. On the left side of the number line is team Negatives, and on the right side is team Positives. Every integer fighting in the colosseum belongs to one of these two teams.

At the start of the battle, the contestants line up outside the colosseum. One by one, they enter and follow these rules:

If there are no contestants from the other team, this contestant waits and becomes the most recent contestant to have entered the colosseum.
If at least one contestant from the opposing team is in the colosseum, this contestant fights the opposing contestant who entered most recently. In a fight between a negative and a positive integer, the one with the larger absolute value wins. After the fight, the winner's value becomes the sum of the two fighting integers, and the loser leaves. If the two integers have the same absolute value, both leave. If there is a winner, the fight continues as long as more opposing contestants remain. Otherwise, the contestant waits.

After all the integers have entered the colosseum, only one team can be declared the winner. Given the lineup, determine which team triumphs and the state of the colosseum after all fights have finished.

Input

The first line contains a single integer $N$ ( $1 \le N \le 5 \cdot 10^5$ ), the number of contestants who enter the colosseum. The second line contains $N$ space-separated integers $x_1, x_2, \dots, x_N$ ( $1 \le |x_i| \le 10^6$ for each $1 \le i \le N$ ), the value of the $i$ th contestant to enter.

Output

Print the winning team as either Positives win! or Negatives win!. On the next line, print the integers remaining in the colosseum after all fighting has finished, in the order they arrived.

If neither team wins, print Tie! instead.

Hint

In Sample Input 1, $N=4$ , and the contestants line up in the order $[-3, -4, 9, 1]$ .

First, contestant $-3$ enters, and the colosseum contains $(-3)$ .
Next, contestant $-4$ enters, and the colosseum contains $(-3, -4)$ .
Then $9$ enters and fights $-4$ . Contestant $9$ wins and becomes $5$ , while $-4$ loses and leaves. Then $5$ fights $-3$ , wins, and becomes $2$ , while $-3$ loses and leaves. The colosseum now contains $(2)$ .
Finally, $1$ enters. The final state is $(2, 1)$ , and Positives win!

Examples3

Example 1
Input
```
4
-3 -4 9 1
```
Expected output
```
Positives win!
2 1
```
Example 2
Input
```
7
4 -2 -2 2 -1 -1 -1
```
Expected output
```
Negatives win!
-1
```
Example 3
Input
```
6
10 -2 -2 -2 -2 -2
```
Expected output
```
Tie!
```