题目描述

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

长度为 $N$、仅由 0 和 1 组成的字符串 $S$ 是否为好字符串，按照如下方式判定：

• 构造数列 $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$ 项中的最大值。

请判断是否存在好字符串，若存在请输出字典序最小的一个。

输入格式

输入从标准输入读入，格式如下：

$N$ $P_1$ $P_2$ $...$ $P_N$

输出格式

若不存在好字符串，则输出 -1。若存在，则输出字典序最小的好字符串。

样例 1

输入

6
3 1 4 6 2 5

输出

001001

样例 2

输入

5
1 2 3 4 5

输出

-1

样例 3

输入

7
1 3 2 5 6 4 7

输出

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

输出

000000000001100101010010011101

说明/提示

限制

• $1\leq N\leq 2\times 10^5$
• $1\leq P_i\leq N$
• $P_1,\ P_2,\ ...,\ P_N$ 互不相同。
• 输入均为整数。

样例解释 1

若取 $S=$ 001001，则 $X=(3,\ 1,\ 6,\ 2)$，$Y=(4,\ 5)$。$X$ 中的高项为第 $1$ 项和第 $3$ 项。$Y$ 中的高项为第 $1$ 项和第 $2$ 项。高项个数相等，因此 001001 是好字符串。不存在字典序更小的好字符串，所以答案为 001001。

由 ChatGPT 4.1 翻译