给你一个数组 $$$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$$$。
示例
输入复制
361 3 5 4 7 2413 10 12 2071 2 3 4 5 6 7
输出复制
100011 1101 1000001
注意
在第一个示例中,您可以首先选择大小 $$$3$$$ 的前缀。然后数组就转化为
| 1 | 4 | 7 | 2 |
| 1 | 4 | 7 |
| 1 |
可以证明$$$a$$$ 不可能转化为$$$[3]$$$。