← 返回题目列表

Codeforces · 1450/D

D. 额定压缩

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

在竞技编程平台 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]$$$ 并且它是一个排列。