Description

There are $n$ balls arranged in a row, numbered from $1$ to $n$ from left to right. Initially, each ball is red. The initial weight of the $i$-th ball is $p_i$. It is guaranteed that $\bm{n}$ is an odd number and that $\bm{p}$ is a permutation of $\bm{1 \sim n}$.

You need to perform exactly $\frac{n - 1}{2}$ operations. In one operation, you must:

• Choose a red ball $i$ such that there is at least one red ball in the range $1 \sim i - 1$ and at least one red ball in the range $i + 1 \sim n$.
• Let $j$ be the largest integer such that $j < i$ and the ball at position $j$ is red, and let $k$ be the smallest integer such that $k > i$ and the ball at position $k$ is red. You will paint both balls $i$ and $k$ blue.
• Then, perform exactly one of the following two operations:
  • Modify $p_j$ (the weight of ball $j$) to $\max(p_i, p_j, p_k)$;
  • Modify $p_j$ (the weight of ball $j$) to $\min(p_i, p_j, p_k)$.

After performing $\frac{n - 1}{2}$ operations, there will be exactly one red ball left.

You need to determine for each positive integer $x$ in the range $1$ to $n$ whether it is possible to perform the operations in such a way that the weight of the remaining red ball is $x$.

Input Format

This problem has multiple test cases in a single test.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ positive integers $p_1, p_2, \ldots, p_n$.

Output Format

For each test case, output a line containing a $01$ string. For each positive integer $i$ in the range $1 \sim n$, if it is possible to perform the operations in such a way that the weight of the remaining red ball is $i$, then the $i$-th position of this $01$ string will be $1$; otherwise, it will be $0$.

4
3
3 2 1
5
1 3 5 2 4
5
5 4 3 1 2
9
4 7 3 6 1 2 5 8 9

101
11111
11101
111111101

Hint

Sample Explanation

For the first test case, the initial state of the balls (color and weight) is $\color{red}{3\ 2\ 1}$.

You need to perform $1$ operation. In this operation, you can only choose ball $2$ and paint both balls $2$ and $3$ blue.

• If you choose to modify $p_1$ to $\max(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{3}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $3$;
• If you choose to modify $p_1$ to $\min(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{1}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $1$.

Thus, you will output a $01$ string that has $1$s at the $1$st and $3$rd positions, and $0$s in the other positions.

For the second test case, it can be easily proven that the weight of the remaining red ball can take all positive integers from $1$ to $n$. Here is an example of a sequence of operations that results in the remaining red ball having a weight of $2$:

• The initial state of the balls is $\color{red}{1\ 3\ 5\ 2\ 4}$.
• Choose ball $2$, paint both balls $2$ and $3$ blue, and set $p_1$ to $\max(p_1, p_2, p_3) = 5$. After this operation, the state of the balls becomes $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$.
• Choose ball $4$, paint both balls $4$ and $5$ blue, and set $p_1$ to $\min(p_1, p_4, p_5) = 2$. After this operation, the state of the balls becomes $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$.

Subtasks and Constraints

• Special Property A: $p_i = i$.

For all tests, it is guaranteed that:

• $1 \le T \le 10^5$;
• $3 \le n \le 10^6 - 1$ and $n$ is an odd number;
• $\sum n \le 10^6$;
• $p$ is a permutation of $1 \sim n$.