给定一个正奇数 N,以及 1,2,…,N 的一个排列 P=(P1,P2,…,PN)。
你有一个序列 A,初始时 A=P。可以反复进行以下操作:
- 选择 A 中一个长度为奇数的连续子序列,设它的中位数为 m。删除这个子序列,并在原位置插入 m。
更严格地说,选择整数 l,r,满足 1≤l≤r≤∣A∣ 且 r−l+1 为奇数。设 m 是 Al,…,Ar 的中位数,将 A 替换成
(A1,…,Al−1,m,Ar+1,…,A∣A∣).
对于每个 k=1,2,…,N,判断能否通过这些操作把 A 变成只含一个元素的序列 (k)。
共有 T 组测试用例,请分别求解。
输入格式
第一行包含一个整数 T。
接下来依次给出 T 组测试用例。每组包含两行:
N
P_1 P_2 ... P_N
输出格式
输出 T 行。对于每组测试用例,输出一个长度为 N 的二进制字符串。
第 k 个字符为 1 表示能够把序列变成 (k),否则为 0。
数据范围
- 1≤T≤104;
- 3≤N≤2×105,且 N 为奇数;
- P 是 1,2,…,N 的排列;
- 所有测试用例的 N 之和不超过 2×105;
- 所有输入值均为整数。
样例输入 1
2
5
2 3 1 5 4
7
7 6 3 4 5 2 1
样例输出 1
00110
0101010
样例说明
第一组中:
- 对于 k=3,选择 (l,r)=(1,5),可以直接把 A 变成 (3)。
- 对于 k=4,先选择 (l,r)=(1,3),得到 (2,5,4);再次选择 (l,r)=(1,3),得到 (4)。
- 对于 k=1,2,5,不存在满足要求的操作序列。