Slime and Hats

题意翻译

有 $n$ 个人从前到后坐成一列，每个人头上都戴着白色或黑色的帽子。 对于第 $i$ 个人，他能够看到位于他前面的 $i-1$ 个人的帽子。 每一轮开始时，所有人都会知道场上是否仍有戴着黑帽的人。每个人都很聪明，如果一个人在某一轮知道了自己的帽子颜色，那么他就会离开。 对于一个人，他能够看到自己前面有谁离开了，能够听到自己后面有多少个人离开了。 现在已经进行了一场游戏，但是 Slime 忘记了每个人头上的帽子颜色，而且他只记下了一部分人的离开时间。 对于第 $i$ 个人，他会给出其离开时间 $t_i$ ，如果他忘记了这个人的离开时间，那么 $t_i=0$ 。 请求出一个所有人帽子颜色的方案，使得每个人的离开时间与给出的 $t$ 相符。

题目描述

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.

输入输出样例

输入样例 #1

5
0 1 1 0 0

输出样例 #1

00000

输入样例 #2

5
0 2 2 0 0

输出样例 #2

00001

输入样例 #3

5
0 0 0 0 0

输出样例 #3

00000

输入样例 #4

5
4 4 0 4 4

输出样例 #4

00100

说明

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.