[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$ 的排列。

[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_e $ (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` と出力せよ。 存在するならば、その中で辞書順最小のものを出力せよ。

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` が答えになります。