题目描述

给定一个由 互不相同整数 组成的数组 $a$。每次操作可选择以下两种之一：

• 选择 $a$ 的一个非空前缀$^{\text{∗}}$，将其替换为该前缀的最小值。
• 选择 $a$ 的一个非空后缀$^{\text{†}}$，将其替换为该后缀的最大值。

注意：你可以选择整个数组 $a$ 作为操作对象。

对于每个元素 $a_i$，判断是否存在操作序列将 $a$ 转化为单元素数组 $[a_i]$，即最终数组 $a$ 仅包含元素 $a_i$。

输出长度为 $n$ 的二进制字符串，第 $i$ 位为 1 表示可行，否则为 0。

$^{\text{∗}}$ 前缀指前 $k$ 个元素组成的子数组（$k \geq 1$）。
$^{\text{†}}$ 后缀指后 $k$ 个元素组成的子数组（$k \geq 1$）。

输入格式

• 第一行：$t$（$1 \leq t \leq 10^4$），测试用例数
• 每个测试用例包含两行：
  • 第一行：$n$（$2 \leq n \leq 2 \cdot 10^5$）—— 数组 $a$ 的长度。
  • 第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）, 保证 $a$ 中数互不相同。
• 所有测试用例的 $n$ 总和不超过 $2 \cdot 10^5$。

输出格式

• 对于每个测试用例，输出一个长度为 $n$ 的二进制字符串——其中第 $i$ 个字符为 $1$ 表示存在可行操作序列，否则为 $0$。

说明/提示

初始数组 $[1,3,5,4,7,2]$ 。

1. 选择前缀 $[1,3,5]$ → 替换为 $\min(1,3,5)=1$ → $[1,4,7,2]$；
2. 选择后缀 $[7,2]$ → 替换为 $\max(7,2)=7$ → $[1,4,7]$；
3. 选择前缀 $[1,4,7]$ → 替换为 $1$ → $[1]$。

可证 $a_1=1$ 可达，$a_2=3$ 不可达（输出第2位为0）。

样例

3
6
1 3 5 4 7 2
4
13 10 12 20
7
1 2 3 4 5 6 7

100011
1101
1000001