CF1841B Keep it Beautiful

如果一个数组 $[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 翻译