配点 : 100 点
問題文
积极奇数 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 测试用例,因此请逐一回答。
制約
- 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 以下
- 所有输入均为整数
部分点
- 额外约束“ 1 包含在输入文件中的 N 的总和是 5000 以下」满足的数据集答对时 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
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
2 5 2 3 1 5 4 7 7 6 3 4 5 2 1
出力例 1
00110 0101010
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 的时候不存在那样的操作序列。