← 返回题目列表

Codeforces · 1841/B

B. 保持美丽

中文机器翻译题面 查看原题

数组 $$$[a_1, a_2, \dots, a_k]$$$ 被称为漂亮的,如果可以从数组开头删除几个(可能是零)元素,并将所有这些元素以相同的顺序插入到数组的后面,从而使结果数组按非降序排序。

换句话说,如果 [0, k-1]$$$ 中存在一个整数 $$$i \ 使得数组 $$$[a_{i+1}, a_{i+2}, \dots, a_{k-1}, a_k, a_1, a_2, \dots, 则数组 $$$[a_1, a_2, \dots, a_k]$$$ 是漂亮的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]$$$ 并不漂亮。

请注意,任何由零个元素或一个元素组成的数组都很漂亮。

给定一个数组 $$$a$$$,它最初是空的。您必须处理对其的 $$$q$$$ 查询。在第 $$$i$$$ 次查询期间,您将获得一个整数 $$$x_i$$$,并且您必须执行以下操作:

- 如果你可以将整数 $$$x_i$$$ 附加到数组 $$$a$$$ 的后面,以便数组 $$$a$$$ 保持美观,那么你必须附加它;
- 否则,什么也不做。

每次查询后,报告您是否附加了给定的整数 $$$x_i$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。第二行包含 $$$q$$$ 整数 $$$x_1, x_2, \dots, x_q$$$ ($$$0 \le x_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印一个由 $$$q$$$ 字符组成的字符串。如果您在第 $$$i$$$ 查询期间附加整数,则字符串的第 $$$i$$$ 个字符应为 1;否则,它应该是 0。

示例

输入 #1

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

输出 #1

111110010
11111
11011

注意

考虑示例的第一个测试用例。最初,数组是$$$[]$$$。

- 尝试附加一个整数 $$$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$$$。