配点 : $1400$ 点

問題文

$(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$ を空の数列とする。
• 各 $i=1,\ 2,\ ...\ N$ について、この順に、$S_i=$ 0 なら $X$ の末尾に、$S_i=$ 1 なら $Y$ の末尾に $P_i$ を追加する。
• $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$ の中で高い項は、$1$ 項目と $3$ 項目です。 また、$Y$ の中で高い項は、$1$ 項目と $2$ 項目です。 高い項の数が等しいので、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