题目背景

English statement. You must submit your code at the Chinese version of the statement.

世界が鮮やかに 染まって

题目描述

有 $n$ 个球排成一排，从左到右依次编号为 $1 \sim n$。每个球初始都是红色的。第 $i$ 个球的初始权值为 $p_i$。保证 $\bm{n}$ 为奇数且 $\bm{p}$ 是一个 $\bm{1 \sim n}$ 的排列。

你需要恰好进行 $\frac{n - 1}{2}$ 次操作。在一次操作中，你需要：

• 选择一个红色的球 $i$，使得 $1 \sim i - 1$ 中至少有一个红球且 $i + 1 \sim n$ 中至少有一个红球。
• 设 $j$ 为最大的整数使得 $j < i$ 且球 $j$ 为红球，$k$ 为最小的整数使得 $k > i$ 且球 $k$ 为红球。你要将球 $i$ 和球 $k$ 都染成蓝色。
• 然后进行以下两种操作的恰好一个：
  • 将 $p_j$（即球 $j$ 的权值）修改为 $\max(p_i, p_j, p_k)$；
  • 将 $p_j$（即球 $j$ 的权值）修改为 $\min(p_i, p_j, p_k)$。

容易发现进行了 $\frac{n - 1}{2}$ 次操作后恰好剩下一个红球。

你需要对于每个 $1 \sim n$ 的正整数 $x$，求出是否能合理地进行操作，使得最后剩下的红球的权值为 $x$。

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$。

输出格式

对于每组数据，输出一行一个 $01$ 串。对于每个 $1 \sim n$ 的正整数 $i$，若能合理地进行操作使得最后剩下的红球的权值为 $i$，那么这个 $01$ 串的第 $i$ 位为 $1$，否则为 $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

提示

【样例解释】

对于第一组数据，初始的球的状态（颜色和权值）依次为 $\color{red}{3\ 2\ 1}$。

你需要进行 $1$ 次操作。在这次操作中你只能选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色。

• 若你选择将 $p_1$ 修改为 $\max(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{3}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $3$；
• 若你选择将 $p_1$ 修改为 $\min(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{1}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $1$。

所以你输出一个 $01$ 串需要使得第 $1$ 和第 $3$ 位为 $1$，其余位为 $0$。

对于第二组数据，容易证明最后剩下的红球权值可以取 $1 \sim n$ 之间的所有正整数。下面给出一个能使得最后剩下的红球权值为 $2$ 的操作过程：

• 初始的球的状态为 $\color{red}{1\ 3\ 5\ 2\ 4}$。
• 选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色，并将 $p_1$ 赋值为 $\max(p_1, p_2, p_3) = 5$。操作后球的状态变为 $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$。
• 选择球 $4$，将球 $4$ 和球 $5$ 染成蓝色，并将 $p_1$ 赋值为 $\min(p_1, p_4, p_5) = 2$。操作后球的状态变为 $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$。

【数据范围】

本题采用捆绑测试。

子任务编号	$n \le$	$\sum n \le$	特殊性质	分值
$1$	$5$	$10^4$	无	$16$
$2$	$19$			$19$
$3$	$99$	$10^6$
$4$	$10^6 - 1$		A	$3$
$5$			无	$43$

• 特殊性质 A：$p_i = i$。

对于所有数据，满足：

• $1 \le T \le 10^5$；
• $3 \le n \le 10^6 - 1$ 且 $n$ 是奇数；
• $\sum n \le 10^6$；
• $p$ 是一个 $1 \sim n$ 的排列。