题目描述

如果一个数组 $[a_1, a_2, \dots, a_k]$ 满足以下条件，则称其为“美丽”的：可以从数组开头移除若干（可以为零）个元素，并将这些元素按原顺序插入到数组末尾，使得得到的新数组是非递减有序的。

换句话说，数组 $[a_1, a_2, \dots, a_k]$ 是美丽的，当且仅当存在一个整数 $i \in [0, k-1]$，使得数组 $[a_{i+1}, a_{i+2}, \dots, a_k, a_1, a_2, \dots, a_i]$ 是非递减有序的。

例如：

• $[3, 7, 7, 9, 2, 3]$ 是美丽的：我们可以将前四个元素移到末尾，得到 $[2, 3, 3, 7, 7, 9]$，这是非递减有序的；
• $[1, 2, 3, 4, 5]$ 是美丽的：我们可以不移动任何元素，得到 $[1, 2, 3, 4, 5]$，这是非递减有序的；
• $[5, 2, 2, 1]$ 不是美丽的。

注意，任何长度为 $0$ 或 $1$ 的数组都是美丽的。

现在给定一个初始为空的数组 $a$，你需要对其处理 $q$ 次操作。在第 $i$ 次操作中，给定一个整数 $x_i$，你需要：

• 如果可以将 $x_i$ 添加到数组 $a$ 的末尾，并且添加后数组 $a$ 仍然是美丽的，则将 $x_i$ 添加到末尾；
• 否则，不做任何操作。

每次操作后，请输出你是否将 $x_i$ 添加到了数组末尾。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含两行。第一行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$），表示操作次数。第二行包含 $q$ 个整数 $x_1, x_2, \dots, x_q$（$0 \le x_i \le 10^9$）。

输入的额外限制：所有测试用例中 $q$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个仅包含 $q$ 个字符的字符串。第 $i$ 个字符为 $1$ 表示在第 $i$ 次操作中成功添加了整数，否则为 $0$。

说明/提示

以样例的第一个测试用例为例，初始数组为 $[]$。

• 尝试添加整数 $3$。数组 $[3]$ 是美丽的，所以添加 $3$；
• 尝试添加整数 $7$。数组 $[3, 7]$ 是美丽的，所以添加 $7$；
• 尝试添加整数 $7$。数组 $[3, 7, 7]$ 是美丽的，所以添加 $7$；
• 尝试添加整数 $9$。数组 $[3, 7, 7, 9]$ 是美丽的，所以添加 $9$；
• 尝试添加整数 $2$。数组 $[3, 7, 7, 9, 2]$ 是美丽的，所以添加 $2$；
• 尝试添加整数 $4$。数组 $[3, 7, 7, 9, 2, 4]$ 不是美丽的，所以不添加 $4$；
• 尝试添加整数 $6$。数组 $[3, 7, 7, 9, 2, 6]$ 不是美丽的，所以不添加 $6$；
• 尝试添加整数 $3$。数组 $[3, 7, 7, 9, 2, 3]$ 是美丽的，所以添加 $3$；
• 尝试添加整数 $4$。数组 $[3, 7, 7, 9, 2, 3, 4]$ 不是美丽的，所以不添加 $4$。

由 ChatGPT 4.1 翻译

样例

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

111110010
11111
11011