题目描述

$(1,\ 2,\ ...\ N)$ の順列 $P$ が与えられます。

0, 1 からなる長さ $N$ の文字列 $S$ がよい文字列であるかどうかは、以下の様に判定されます。

• 数列 $X$, $Y$ を次のように構築する。
  • まず、$X$, $Y$ を空の数列とする。
  • 各 $i=1,\ 2,\ ...\ N$ について、この順に、$S_i=$ 0 なら $X$ の末尾に、$S_i=$ 1 なら $Y$ の末尾に $P_i$ を追加する。
• $X$ の中にある高い項の個数と $Y$ の中にある高い項の個数が等しいならば、$S$ はよい文字列である。 ここで、ある数列の $i$ 番目の項が高いとは、その項が数列の $1$ 番目から $i$ 番目の項の中で最大であることを意味する。

よい文字列が存在するか判定し、存在するならその中で辞書順最小のものを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

よい文字列が存在しないならば -1 と出力せよ。 存在するならば、その中で辞書順最小のものを出力せよ。

题目大意

题目描述：你有一个$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$ 的排列。

6
3 1 4 6 2 5

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

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ P_i\ \leq\ N$
• $P_1,\ P_2,\ ...\ P_N$ はすべて異なる。
• 入力はすべて整数である。

Sample Explanation 1

$S=$ 001001 とすると、$X=(3,\ 1,\ 6,\ 2)$, $Y=(4,\ 5)$ となります。 $X$ の中で高い項は、$1$ 項目と $3$ 項目です。 また、$Y$ の中で高い項は、$1$ 項目と $2$ 項目です。 高い項の数が等しいので、001001 はよい文字列です。 これより辞書順で小さいよい文字列は存在しないので、001001 が答えになります。