[AGC028E] High Elements

题面翻译

题目描述：你有一个$1,2,\dots,n$ 的排列 $P$。设一个长度为 $n$ 的 $01$ 字符串 $S$ 合法，当且仅当，先设两个空序列 $A,B$，我们按照 $1$ 到 $n$ 的顺序，若 $S$ 当前位为 $1$ 则把当前位的 $P$ 添加到序列 $A$ 的末尾，否则添加到序列 $B$ 的末尾，使得 $A,B$ 的前缀最大值个数相等。求字典序最小的合法字符串 $S$。

数据范围：$n\le 2\times 10^5,P$ 是 $1,2,\dots,n$ 的排列。

输入格式

第一行给出数字N

第二行给出N个数字

输出格式

如题

样例 #1

样例输入 #1

6
3 1 4 6 2 5

样例输出 #1

001001

样例 #2

样例输入 #2

5
1 2 3 4 5

样例输出 #2

-1

样例 #3

样例输入 #3

7
1 3 2 5 6 4 7

样例输出 #3

0001101

样例 #4

样例输入 #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

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ P_i\ \leq\ N$