#P18430. Prefix Mahjong

Prefix Mahjong

Prefix Mahjong

对正整数多重集,定义以下三种组:

  • 刻子(Pong):x,x,x{x,x,x},其中 xx 是正整数。
  • 顺子(Chow):x,x+1,x+2{x,x+1,x+2},其中 xx 是正整数。
  • 雀头(Eyes):x,x{x,x},其中 xx 是正整数。

若一个正整数序列中的所有元素可以被分成若干个刻子、若干个顺子和恰好一个雀头,则称该序列为“Mahjong”。刻子和顺子的数量都可以为零;分组不要求元素在原序列中相邻。

例如,序列 1,1,4,5,1,4,4,3{1,1,4,5,1,4,4,3} 是 Mahjong,因为它可以分成 1,1,1{1,1,1}、4,5,3{4,5,3} 和 4,4{4,4}。

给定一个正整数序列,对它的每个前缀分别判断是否为 Mahjong。序列长度不固定,每种整数的出现次数也没有额外上限。

输入格式

第一行是测试用例数 tt,1≤t≤1051\le t\le10^5。

每个测试用例占一行,先给出长度 nn,随后给出 nn 个正整数 a1,…,ana_1,\ldots,a_n,满足

1≤n≤105,1≤ai≤109.1\le n\le10^5,\qquad1\le a_i\le10^9.

保证所有测试用例的 nn 之和不超过 10510^5。

输出格式

每个测试用例输出一行长度为 nn 的01字符串。第 ii 个字符为1,当且仅当长度为 ii 的前缀是 Mahjong;否则为0。

完整原样例一

输入:

4
8 1 1 4 5 1 4 4 3
14 1 1 3 5 4 2 5 5 4 6 6 2 2 4
17 3 5 3 2 2 3 3 1 4 3 1 3 3 5 2 4 4
8 2 4 11 11 14 8 6 3

输出:

01000001
01001001000001
00000000001000001
00000000

完整原样例二

输入:

10
2 1 1
3 1 1 1
3 1 2 3
5 1 1 1 1 1
5 1 1 1 2 2
5 1 1 1 2 3
8 1 1 1 1 1 1 2 3
5 2 2 1 1 1
5 3 2 1 1 1
8 3 2 1 1 1 1 1 1

输出:

01
010
000
01001
01001
01001
01001001
01001
00001
00001001