CF1349E.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.

史莱姆和奥拉克正在进行一场回合制游戏。在一个大房间里，有 $n$ 名玩家坐在椅子上，面朝同一列，每名玩家都被分配了一个编号：玩家 $1$ 坐在队列最前方，玩家 $2$ 紧坐在他正后方；玩家 $3$ 紧坐在玩家 $2$ 正后方，依此类推；玩家 $n$ 紧坐在玩家 $n-1$ 正后方。每名玩家都戴着一顶帽子，颜色为黑色或白色。由于所有玩家均面朝前方，因此玩家 $i$ 能够知道玩家 $j$ 的帽子颜色 当且仅当 $i > j$。

每轮开始时，奥拉克会宣布房间中是否存在戴着黑帽子的玩家。

奥拉克发言之后，若某位玩家能唯一确定自己帽子的颜色，他便会将自己的帽子放在椅子上，起身离开房间。所有玩家都很聪明，因此只要在本轮及之前各轮所获得的信息足以推断出自己帽子的颜色，他们就一定会推断出来。

在每一轮中，所有已知自己帽子颜色的玩家将同时离开房间。这意味着：一名玩家只有在本轮中因他人离开而获得新信息后才推断出自己帽子颜色时，他只能在下一轮离开。

注意：当玩家离开时，他会先将自己的帽子放回椅子上再离开，因此他前方的玩家仍无法看到他的帽子。

第 $i$ 名玩家确切知道玩家 $1,2,\ldots,i-1$ 中哪些人离开了房间，并且知道玩家 $i+1,i+2,\ldots,n$ 中有多少人已离开房间。

史莱姆站在房间外。他观察玩家依次走出房间，并记录下每位玩家的编号及其离开的轮次。不幸的是，史莱姆非常粗心，只记录了部分数据，且这些数据以如下格式给出：“玩家 $x$ 在第 $y$ 轮离开”。

史莱姆请你帮他推断出每名玩家帽子的颜色。若存在多种可能解，输出任意一种即可。

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.

第一行包含一个整数 $n\ (1\le n\le 200\,000)$。

第二行包含 $n$ 个整数 $t_1,t_2,\dots,t_n\ (0\le t_i\le 10^{15})$。若 $t_i=0$，则表示没有关于玩家 $i$ 的数据；否则表示玩家 $i$ 在第 $t_i$ 轮被淘汰。

对于给定的输入，至少存在一个解。

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.

输出一个长度为 $n$ 的二进制字符串。该字符串的第 $i$ 个字符应为 '1'，当且仅当玩家 $i$ 戴着黑帽子；否则应为 '0'。若存在多个解，输出任意一个即可。

In the first example, for the given solution, all the players wear white hats. In the first turn, Orac tells all the players that there are no players wearing a black hat, so each player knows that he is wearing a white hat, and he will leave in the first turn.

In the second example, for the given solution, the player $5$ wears a black hat, other players wear white hats. Orac tells all the players that there exists a player wearing a black hat, and player $5$ know that the other players are all wearing white hats, so he can infer that he is wearing a black hat; therefore he leaves in the first turn, other players leave in the second turn. Note that other players can infer that they are wearing white hats immediately after player $5$ leaves, but they have to wait for the next turn to leave according to the rule.

In the third example, there is no information about the game, so any output is correct.

在第一个例子中，对于给定的解，所有玩家都戴着白帽子。在第一轮中，Orac 告知所有玩家：没有玩家戴着黑帽子，因此每位玩家都能推断出自己戴的是白帽子，并于第一轮离开。

在第二个例子中，对于给定的解，玩家 $5$ 戴着黑帽子，其余玩家均戴白帽子。Orac 告知所有玩家：存在至少一名玩家戴着黑帽子；而玩家 $5$ 观察到其余所有玩家均戴白帽子，从而推断出自己戴的是黑帽子；因此他于第一轮离开，其余玩家则于第二轮离开。注意：其余玩家虽可在玩家 $5$ 离开后立即推断出自己戴的是白帽子，但根据规则，他们仍需等到下一轮才能离开。

在第三个例子中，题目未提供任何关于游戏的信息，因此任意输出均视为正确。