AT_agc028_e [AGC028E] High Elements

[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/A

N/A

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