得分 : $1400$ 分

问题陈述

给定 $P$，一个 $(1,\ 2,\ ...\ N)$ 的排列。

长度为 $N$ 的字符串 $S$ 由 0 和 1 组成，当满足以下条件时称为 好字符串：

• 序列 $X$ 和 $Y$ 的构造方式如下：
  • 首先，让 $X$ 和 $Y$ 是空序列。
  • 对于每个 $i=1,\ 2,\ ...\ N$，按顺序，如果 $S_i=$ 0，则将 $P_i$ 追加到 $X$ 的末尾；如果 $S_i=$ 1，则将 $P_i$ 追加到 $Y$ 的末尾。
• 如果 $X$ 和 $Y$ 的 高 元素数量相同，则 $S$ 是一个好字符串。
  这里，序列中第 $i$ 个元素称为 高 元素，当该元素是序列中从第 $1$ 个到第 $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。
如果存在，打印字典序最小的字符串。

6
3 1 4 6 2 5

001001

设 $S=$ 001001。那么，$X=(3,\ 1,\ 6,\ 2)$ 和 $Y=(4,\ 5)$。
$X$ 中的高元素是第一个和第三个元素，$Y$ 中的高元素是第一个和第二个元素。
由于它们的高元素数量相同，因此 001001 是一个好字符串。
没有比这更小的字典序好字符串，所以答案是 001001。

5
1 2 3 4 5

-1

7
1 3 2 5 6 4 7

0001101

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

000000000001100101010010011101