Day of the Programmer- HackerRank problem

                                                    Prefix Min and Suffix Max

time limit per test

2 seconds

memory limit per test

256 megabytes

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

In one operation, you may either:

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

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

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

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

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

Input

The first line contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$)  — the number of test cases.

The first line of each test case contains one integer n$n$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$) — the size of the array a$a$.

The second line of each test case contains n$n$ integers, a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤106$1\le a_i\le {10}^6$). It is guaranteed that all ai$a_i$ are distinct.

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

Output

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

Example

Input

Copy

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

Output

Copy

100011
1101
1000001

Note

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

1

4

7

2

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

1

4

7

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

1

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

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

Prefix Min and Suffix Max problem solution by java.

Codeforces round 1034 (Div 3) problems solution.