分数: 1400 点
问题陈述
你被给予 P,排列 (1,\ 2,\ ...\ N).
一个字符串 S 长度 N 组成 0 和 1 是 好字符串 当满足以下条件时:
- 序列
满足条件的 X 和 Y 的构造如下:
- 首先,让 X 和 Y 是空序列。
- 对于每个 i=1,\ 2,\ ...\ N,按此顺序,附加 P_i 到年底 X if S_i=
0,并将其附加到末尾 Y if S_i=1.
- If X 和 Y 有相同数量的 高 元素, S 是一个很好的字符串。 在这里, i序列的第一个元素被称为 高 当该元素是来自 1-st 至 i- 序列中的第一个元素。
确定是否存在好的字符串。如果存在,则找到字典顺序最小的此类字符串。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- P_1,\ P_2,\ ...\ P_N 都是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 ... P_N
输出
如果不存在好的字符串,则打印 -1。
如果存在,则打印按字典顺序最小的此类字符串。
示例输入 1
6 3 1 4 6 2 5
示例输出 1
001001
让 S= 001001。然后, X=(3,\ 1,\ 6,\ 2) 和 Y=(4,\ 5)。
中的高元素 X 是第一个和第三个元素,其中的高元素 Y 是第一个和第二个元素。
由于它们具有相同数量的高元素, 001001 是一个很好的字符串。
没有比这个更小的字符串,所以答案是 001001.
示例输入 2
5 1 2 3 4 5
示例输出 2
-1
示例输入 3
7 1 3 2 5 6 4 7
示例输出 3
0001101
示例输入 4
30 1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30
示例输出 4
000000000001100101010010011101