A13389 | Slime and Hats

Slime and Orac are holding a turn-based game. In a big room, there are $n$ players sitting on the chairs, looking forward to a column and each of them is given a number: player $1$ sits in the front of the column, player $2$ sits directly behind him; player $3$ sits directly behind player $2$ , and so on; player $n$ sits directly behind player $n-1$ . Each player wears a hat that is either black or white. As each player faces forward, player $i$ knows the color of player $j$ 's hat if and only if $i$ is larger than $j$ .

At the start of each turn, Orac will tell whether there exists a player wearing a black hat in the room.

After Orac speaks, if the player can uniquely identify the color of his hat, he will put his hat on the chair, stand up and leave the room. All players are smart, so if it is possible to understand the color of their hat using the obtained information during this and previous rounds, they will understand it.

In each turn, all players who know the color of their hats will leave at the same time in this turn, which means a player can only leave in the next turn if he gets to know the color of his hat only after someone left the room at this turn.

Note that when the player needs to leave, he will put the hat on the chair before leaving, so the players ahead of him still cannot see his hat.

The $i$ -th player will know who exactly left the room among players $1,2,\ldots,i-1$ , and how many players among $i+1,i+2,\ldots,n$ have left the room.

Slime stands outdoor. He watches the players walking out and records the numbers of the players and the time they get out. Unfortunately, Slime is so careless that he has only recorded some of the data, and this given data is in the format "player $x$ leaves in the $y$ -th round".

Slime asked you to tell him the color of each player's hat. If there are multiple solutions, you can find any of them.

The first line contains a integer $n\ (1\le n\le 200\,000)$ .

The second line contains $n$ integers $t_1,t_2,\dots,t_n\ (0\le t_i\le 10^{15})$ . If $t_i=0$ , then there are no data about player $i$ ; otherwise it means player $i$ leaves in the $t_i$ -th round.

At least one solution exists for the given input.

Print one binary string of $n$ characters. The $i$ -th character of the string should be '1' if player $i$ wears a black hat and should be '0', otherwise. If there are multiple solutions, you can print any of them.