AT_tupc2024_j Median Operations

正の**奇数** $ N $ と $ (1, 2, \ldots, N) $ の順列 $ P = (P_1, P_2, \ldots, P_N) $ が与えられます。 あなたははじめ数列 $ A = P $ を持っており、数列 $ A $ に対して以下の操作を繰り返し行うことができます。 - $ A $ の奇数長の連続部分列を選ぶ。選んだ連続部分列の中央値を $ m $ として、 $ A $ から選んだ連続部分列を削除し、その位置に $ m $ を挿入する。 - より厳密には、 $ 1 \leq l \leq r \leq |A| $ かつ $ r-l+1 $ が奇数であるような整数の組 $ (l, r) $ を選ぶ。 $ (A_l, A_{l+1}, \ldots, A_r) $ の中央値を $ m $ として、 $ A $ を $ (A_1, \ldots, A_{l-1}, m, A_{r+1}, \ldots, A_n) $ で置き換える。 各 $ k = 1, 2, \ldots, N $ について、操作を繰り返すことで $ A $ を長さ $ 1 $ の数列 $ (k) $ にすることができるか判定してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ ここで $ \text{case}_i $ は $ i $ 番目のテストケースを表し、各テストケースは以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースの答えを長さ $ N $ の文字列で出力せよ。 文字列の $ k $ 文字目は、操作を繰り返すことで数列を $ (k) $ にすることができるならば `1` 、そうでないならば `0` とせよ。

### 部分点 - 追加の制約「 $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 5000 $ 以下」を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ つ目のテストケースについて - $ k = 3 $ のとき : $ (l, r) = (1, 5) $ を選ぶことで $ A = (3) $ になります。 - $ k = 4 $ のとき : $ (l, r) = (1, 3) $ を選び $ A = (2, 5, 4) $ にしたのち、 $ (l, r) = (1, 3) $ を選ぶことで $ A = (4) $ になります。 - $ k = 1, 2, 5 $ のときはそのような操作列が存在しません。 ### Constraints - $ 1 \leq T \leq {10}^4 $ - $ 3 \leq N \leq 2 \times {10}^5 $ - $ N $ は奇数 - $ (P_1, P_2, \ldots, P_N) $ は $ (1, 2, \ldots, N) $ の順列 - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 2 \times {10}^5 $ 以下 - 入力はすべて整数