You are given an array $$$a$$$ of distinct integers.

In one operation, you may either:

choose a nonempty prefix$$$^{\text{∗}}$$$ of $$$a$$$ and replace it with its minimum value, or
choose a nonempty suffix$$$^{\text{†}}$$$ of $$$a$$$ and replace it with its maximum value.

Note that you may choose the entire array $$$a$$$.

For each element $$$a_i$$$, determine if there exists some sequence of operations to transform $$$a$$$ into $$$[a_i]$$$; that is, make the array $$$a$$$ consist of only one element, which is $$$a_i$$$. Output your answer as a binary string of length $$$n$$$, where the $$$i$$$-th character is $$$1$$$ if there exists a sequence to transform $$$a$$$ into $$$[a_i]$$$, and $$$0$$$ otherwise.

$$$^{\text{∗}}$$$A prefix of an array is a subarray consisting of the first $$$k$$$ elements of the array, for some integer $$$k$$$.

$$$^{\text{†}}$$$A suffix of an array is a subarray consisting of the last $$$k$$$ elements of the array, for some integer $$$k$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers, $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). It is guaranteed that all $$$a_i$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output a binary string of length $$$n$$$ — the $$$i$$$-th character should be $$$1$$$ if there exists a sequence of operations as described above, and $$$0$$$ otherwise.

Note

In the first sample, you can first choose the prefix of size $$$3$$$. Then the array is transformed into

1

4

7

2

Next, you can choose the suffix of size $$$2$$$. Then the array is transformed into

1

4

7

Finally, you can choose the prefix of size $$$3$$$. Then the array is transformed into

1

So we see that it is possible to transform $$$a$$$ into $$$[1]$$$.

It can be shown that it is impossible to transform $$$a$$$ into $$$[3]$$$.

Prefix Min and Suffix Max

Examples