Tower Game

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are playing a game with a set of towers arranged in a row. Each tower has a certain number of floors \(h_i\).

At the beginning of the game, a marble is located on the first floor of one of the towers. In one turn, a player can:

1. Move the marble 1 floor higher on the same tower, if such floor exists.

2. Move the marble to the same floor of an adjacent tower to the left or right, if possible.

For example, if the marble is on the 4th floor of the 7th tower, then in one turn it can be moved either to the 5th floor of the 7th tower, or to the 4th floor of the 6th tower, or to the 4th floor of the 8th tower. Each of the moves can only be made if the corresponding floor exists.

The players take turns, Marichka makes the first move. The player who cannot make a move loses. If no winner is determined after \(47^{74}\) turns, a draw is declared. Help Zenyk and Marichka determine for each tower who will win if the marble is initially located on the 1st floor of that tower.

Input

The first line contains a single integer \(n\) — the number of towers.

The second line contains \(n\) integers \(h_i\) — the heights of the towers.

Output

Print a single string of \(n\) characters. The \(i\)-th character should be 1 if the first player (Marichka) wins, 2 if the second (Zenyk) wins, and 0 if the game ends in a draw.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le h_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 2 1	212

Input (stdin) сopy	Output (stdout) сopy
4 1 1 1 1	0000

Notes

In the first example, if the game starts at the first tower, the first player is forced to move the marble to the 2nd tower, the second player moves the marble one floor higher and wins. If the game starts at the second tower, the first player moves the marble one floor higher and wins.

In the second example, players can move the marble between towers an infinite number of times, so the game will end in a draw for all starting towers.