给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p=[p_1, p_2, \ldots, p_n]$$$。我们称数字 $$$m$$$ ($$$1 \le m \le n$$$) 漂亮,如果存在两个索引 $$$l, r$$$ ($$$1 \le l \le r \le n$$$),使得数字 $$$[p_l, p_{l+1}, \ldots, p_r]$$$ 是数字 $$$1, 2, \ldots 的排列,米$$$。
例如,令 $$$p = [4, 5, 1, 3, 2, 6]$$$。在这种情况下,数字 $$$1, 3, 5, 6$$$ 很漂亮,而 $$$2, 4$$$ 则不然。这是因为:
- 如果 $$$l = 3$$$ 且 $$$r = 3$$$,我们将得到 $$$m = 1$$$ 的排列 $$$[1]$$$;
- 如果 $$$l = 3$$$ 且 $$$r = 5$$$ 我们将得到一个排列 $$$[1, 3, 2]$$$ for $$$m = 3$$$;
- 如果 $$$l = 1$$$ 且 $$$r = 5$$$ 我们将得到一个排列 $$$[4, 5, 1, 3, 2]$$$ for $$$m = 5$$$;
- 如果 $$$l = 1$$$ 且 $$$r = 6$$$ 我们将得到一个排列 $$$[4, 5, 1, 3, 2, 6]$$$ for $$$m = 6$$$;
- 不可能采用一些 $$$l$$$ 和 $$$r$$$,使得 $$$[p_l, p_{l+1}, \ldots, p_r]$$$ 是数字 $$$1, 2, \ldots, m$$$ 的排列,对于 $$$m = 2$$$ 和 $$$m = 4$$$。
给你一个排列 $$$p=[p_1, p_2, \ldots, p_n]$$$。对于所有 $$$m$$$ ($$$1 \le m \le n$$$) 确定它是否是一个漂亮的数字。
输入
第一行包含唯一的整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 输入中测试用例的数量。接下来的几行包含测试用例的描述。
测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 给定排列 $$$p$$$ 的长度。下一行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$,所有 $$$p_i$$$ 都不同)——给定的排列 $$$p$$$。
保证输入中所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$t$$$ 行 - 按照输入中给出的顺序测试用例的答案。
测试用例的答案是长度为 $$$n$$$ 的字符串,如果 $$$i$$$ 是一个漂亮的数字,则第 $$$i$$$ 个字符等于 $$$1$$$;如果 $$$i$$$ 不是一个漂亮的数字,则等于 $$$0$$$。
示例
输入 #1
3 6 4 5 1 3 2 6 5 5 3 1 2 4 4 1 4 3 2
输出 #1
101011 11111 1001
注意
第一个测试用例在问题陈述中进行了描述。
在第二个测试用例中,从 $$$1$$$ 到 $$$5$$$ 的所有数字都很漂亮:
- 如果 $$$l = 3$$$ 且 $$$r = 3$$$,我们将得到 $$$m = 1$$$ 的排列 $$$[1]$$$;
- 如果 $$$l = 3$$$ 且 $$$r = 4$$$ 我们将得到 $$$[1, 2]$$$ 的排列 $$$m = 2$$$;
- 如果 $$$l = 2$$$ 且 $$$r = 4$$$ 我们将得到一个排列 $$$[3, 1, 2]$$$ for $$$m = 3$$$;
- 如果 $$$l = 2$$$ 且 $$$r = 5$$$ 我们将得到一个排列 $$$[3, 1, 2, 4]$$$ for $$$m = 4$$$;
- 如果 $$$l = 1$$$ 且 $$$r = 5$$$,则 $$$m = 5$$$ 的排列为 $$$[5, 3, 1, 2, 4]$$$。