在竞技编程平台 CodeCook 上,每个人都有一个由长度为 $$$n$$$ 的整数数组 $$$a$$$ 描述的评级图。您现在正在更新基础架构,因此您已经创建了一个程序来压缩这些图。
该程序的工作原理如下。给定一个整数参数 $$$k$$$,程序会取 $$$a$$$ 中长度为 $$$k$$$ 的每个连续子数组的最小值。
更正式地,对于长度为 $$$n$$$ 的数组 $$$a$$$ 和整数 $$$k$$$,将 $$$a$$$ 的 $$$k$$$ 压缩数组定义为长度为 $$$n-k+1$$$ 的数组 $$$b$$$,使得 $$$$$$b_j =\min_{j\le i\le j+k-1}a_i$$$$$$
例如$$$[1, 3, 4, 5, 2]$$$的$$$3$$$压缩数组为$$$[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}]=[1, 3, 2].$$$
长度 $$$m$$$ 的排列是一个由 $$$m$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$m$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$m=3$$$ 但数组中有 $$$4$$$)。
如果 $$$k$$$ 压缩数组是一个排列,那么 CodeCook 用户会很高兴。给定一个数组 $$$a$$$,确定所有 $$$1\leq k\leq n$$$ 在对该数组进行 $$$k$$$ 压缩后 CodeCook 用户是否满意。
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 3\cdot 10^5$$$) — 数组的长度。
每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。
输出
对于每个测试用例,打印长度为 $$$n$$$ 的二进制字符串。
如果 CodeCook 用户在对数组 $$$a$$$ 进行 $$$k$$$ 压缩后感到满意,则字符串的第 $$$k$$$ 个字符应为 $$$1$$$,否则为 $$$0$$$。
示例
输入 #1
5 5 1 5 3 4 2 4 1 3 2 1 5 1 3 3 3 2 10 1 2 3 4 5 6 7 8 9 10 3 3 3 2
输出 #1
10111 0001 00111 1111111111 000
注意
在第一个测试用例中,$$$a=[1, 5, 3, 4, 2]$$$。
- $$$a$$$ 的 $$$1$$$ 压缩是 $$$[1, 5, 3, 4, 2]$$$ 并且它是一个排列。
- $$$a$$$ 的 $$$2$$$ 压缩是 $$$[1, 3, 3, 2]$$$ 并且它不是排列,因为 $$$3$$$ 出现了两次。
- $$$a$$$ 的 $$$3$$$ 压缩是 $$$[1, 3, 2]$$$ 并且它是一个排列。
- $$$a$$$ 的 $$$4$$$ 压缩是 $$$[1, 2]$$$ 并且它是一个排列。
- $$$a$$$ 的 $$$5$$$ 压缩是 $$$[1]$$$ 并且它是一个排列。