#P18328. Median Operations

Median Operations

Median Operations

给定一个正奇数 NN,以及 1,2,…,N1,2,\ldots,N 的一个排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N)。

你有一个序列 AA,初始时 A=PA=P。可以反复进行以下操作:

  • 选择 AA 中一个长度为奇数的连续子序列,设它的中位数为 mm。删除这个子序列,并在原位置插入 mm。

更严格地说,选择整数 l,rl,r,满足 1≤l≤r≤∣A∣1\le l\le r\le |A| 且 r−l+1r-l+1 为奇数。设 mm 是 Al,…,ArA_l,\ldots,A_r 的中位数,将 AA 替换成

(A1,…,Al−1,m,Ar+1,…,A∣A∣).(A_1,\ldots,A_{l-1},m,A_{r+1},\ldots,A_{|A|}).

对于每个 k=1,2,…,Nk=1,2,\ldots,N,判断能否通过这些操作把 AA 变成只含一个元素的序列 (k)(k)。

共有 TT 组测试用例,请分别求解。

输入格式

第一行包含一个整数 TT。

接下来依次给出 TT 组测试用例。每组包含两行:

N
P_1 P_2 ... P_N

输出格式

输出 TT 行。对于每组测试用例,输出一个长度为 NN 的二进制字符串。

第 kk 个字符为 1 表示能够把序列变成 (k)(k),否则为 0。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 3≤N≤2×1053\le N\le2\times10^5,且 NN 为奇数;
  • PP 是 1,2,…,N1,2,\ldots,N 的排列;
  • 所有测试用例的 NN 之和不超过 2×1052\times10^5;
  • 所有输入值均为整数。

样例输入 1

2
5
2 3 1 5 4
7
7 6 3 4 5 2 1

样例输出 1

00110
0101010

样例说明

第一组中:

  • 对于 k=3k=3,选择 (l,r)=(1,5)(l,r)=(1,5),可以直接把 AA 变成 (3)(3)。
  • 对于 k=4k=4,先选择 (l,r)=(1,3)(l,r)=(1,3),得到 (2,5,4)(2,5,4);再次选择 (l,r)=(1,3)(l,r)=(1,3),得到 (4)(4)。
  • 对于 k=1,2,5k=1,2,5,不存在满足要求的操作序列。