Prefix Mahjong
本题没有可用的提交语言。
Description
A positive integer multiset $s$ is a "Pong" if $s=\{x,x,x\}$ for some positive integer $x$.
A positive integer multiset $s$ is a "Chow" if $s=\{x,x+1,x+2\}$ for some positive integer $x$.
A positive integer multiset $s$ is an "Eyes" if $s=\{x,x\}$ for some positive integer $x$.
A positive integer sequence is a "Mahjong" if it can be divided into some (possibly zero) "Pong"s, some (possibly zero) "Chow"s, and exactly one "Eyes".
For example, sequence $s=\{1,1,4,5,1,4,4,3\}$ is a "Mahjong" because it can be divided into $\{1,1,1\}$, $\{4,5,3\}$, $\{4,4\}$.
For each prefix of a given positive integer sequence, determine if it is a "Mahjong".
Each test contains multiple test cases. The first line contains a single interger $t$ ($1 \leq t \leq 10^5$), denoting the number of test cases.
For each test case, the only line contains an integer $n$ ($1\le n\le 10^5$) and the following $n$ positive integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le 10^9$), denoting the length of the integer sequence and the elements of the positive integer sequence, respectively.
It is guaranteed that the sum of $n$ over all testcases does not exceed $10^5$.
For each test case, print a string consisting of '0' and '1' in one line. The $i$-th character is '1' if the prefix of length $i$ is a "Mahjong"; otherwise it is '0'.
Input
Each test contains multiple test cases. The first line contains a single interger $t$ ($1 \leq t \leq 10^5$), denoting the number of test cases.
For each test case, the only line contains an integer $n$ ($1\le n\le 10^5$) and the following $n$ positive integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le 10^9$), denoting the length of the integer sequence and the elements of the positive integer sequence, respectively.
It is guaranteed that the sum of $n$ over all testcases does not exceed $10^5$.
Output
For each test case, print a string consisting of '0' and '1' in one line. The $i$-th character is '1' if the prefix of length $i$ is a "Mahjong"; otherwise it is '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
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
01000001
01001001000001
00000000001000001
00000000
01
010
000
01001
01001
01001
01001001
01001
00001
00001001