数组 $$$[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$$$。