史莱姆和奥拉克正在进行回合制游戏。在一个大房间里,有$$$n$$$玩家坐在椅子上,期待着一个柱子,每个人都有一个编号:玩家$$$1$$$坐在柱子的前面,玩家$$$2$$$坐在他的正后面;玩家 $$$3$$$ 直接坐在玩家 $$$2$$$ 后面,依此类推;玩家 $$$n$$$ 直接坐在玩家 $$$n-1$$$ 后面。每个玩家都戴着一顶黑色或白色的帽子。当每个玩家面向前方时,当且仅当 $$$i$$$ 大于 $$$j$$$ 时,玩家 $$$i$$$ 知道玩家 $$$j$$$ 帽子的颜色。
每回合开始时,Orac都会判断房间内是否存在戴黑帽子的玩家。
Orac说话后,如果玩家能够唯一识别自己帽子的颜色,他会将帽子放在椅子上,站起来离开房间。所有玩家都很聪明,所以如果能够利用本轮和前几轮获得的信息来理解他们帽子的颜色,他们就会理解。
在每个回合中,所有知道自己帽子颜色的玩家都会在本回合中同时离开,这意味着玩家只有在本回合有人离开房间后才知道自己帽子的颜色,才能在下回合离开。
注意,当玩家需要离开时,他会在离开前将帽子放在椅子上,因此他前面的玩家仍然看不到他的帽子。
第$$$i$$$个玩家将知道$$$1,2,\ldots,i-1$$$中的玩家到底是谁离开了房间,以及$$$i+1,i+2,\ldots,n$$$中有多少个玩家离开了房间。
史莱姆站在户外。他看着球员们走出去,记录下球员的人数和他们走出去的时间。不幸的是,史莱姆太粗心了,他只记录了部分数据,而这个给出的数据的格式是“玩家$$$x$$$在第$$$y$$$第轮离开”。
史莱姆让你告诉他每个玩家帽子的颜色。如果有多个解决方案,您可以找到其中任何一个。
输入
第一行包含一个整数 $$$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$$$ 轮中离开。
对于给定的输入,至少存在一个解决方案。
输出
打印一个由 $$$n$$$ 个字符组成的二进制字符串。如果玩家 $$$i$$$ 戴黑帽子,则字符串的第 $$$i$$$ 个字符应为“1”,否则应为“0”。如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #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
注意
在第一个示例中,对于给定的解决方案,所有玩家都戴着白帽子。在第一个回合中,Orac告诉所有玩家没有戴黑帽子的玩家,因此每个玩家都知道自己戴着白帽子,并且他会在第一个回合中离开。
在第二个示例中,对于给定的解决方案,玩家 $$$5$$$ 戴着黑帽子,其他玩家戴着白帽子。 Orac告诉所有玩家存在一个戴着黑帽子的玩家,并且玩家$$$5$$$知道其他玩家都戴着白帽子,因此他可以推断自己戴着黑帽子;因此他在第一回合离开,其他玩家在第二回合离开。请注意,其他玩家可以在$$$5$$$玩家离开后立即推断出他们戴着白帽子,但根据规则他们必须等待下一轮离开。
在第三个示例中,没有有关游戏的信息,因此任何输出都是正确的。