← 返回题目列表

Codeforces · 2123/C

C. 前缀最小和后缀最大

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

给你一个数组 $$$a$$$ 不同 整数。

在一次操作中,您可以:

  • 选择一个非空 前缀$$$^{\text{∗}}$$$ of $$$a$$$ 并将其替换为其最小值,或
  • 选择一个非空 后缀$$$^{\text{†}}$$$ 的 $$$a$$$ 并将其替换为其最大值。

请注意,您可以选择整个数组 $$$a$$$。

对于每个元素 $$$a_i$$$,确定是否存在某种操作序列将 $$$a$$$ 转换为 $$$[a_i]$$$;也就是说,使数组$$$a$$$仅包含一个元素,即$$$a_i$$$。将答案输出为长度为 $$$n$$$ 的二进制字符串,其中如果存在将 $$$a$$$ 转换为 $$$[a_i]$$$ 的序列,则第 $$$i$$$ 个字符为 $$$1$$$,否则为 $$$0$$$。

$$$^{\text{*}}$$$A 数组的 前缀 是由数组的前 $$$k$$$ 元素组成的子数组,对于某个整数 $$$k$$$。

$$$^{\text{†}}$$$A 数组的 后缀 是由数组的最后 $$$k$$$ 元素组成的子数组,对于某个整数 $$$k$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$)。保证所有 $$$a_i$$$ 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串 - 如果存在如上所述的操作序列,则第 $$$i$$$ 个字符应为 $$$1$$$,否则为 $$$0$$$。

示例

输入
复制

3
6
1 3 5 4 7 2
4
13 10 12 20
7
1 2 3 4 5 6 7

输出
复制

100011
1101
1000001

注意

在第一个示例中,您可以首先选择大小 $$$3$$$ 的前缀。然后数组就转化为

1472
接下来,您可以选择大小$$$2$$$的后缀。然后数组就转化为
147
最后,您可以选择大小$$$3$$$的前缀。然后数组就转化为
1
所以我们看到可以将 $$$a$$$ 转换为 $$$[1]$$$。

可以证明$$$a$$$ 不可能转化为$$$[3]$$$。