Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Beautiful Numbers

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a permutation $$$p=[p_1, p_2, \ldots, p_n]$$$ of integers from $$$1$$$ to $$$n$$$. Let's call the number $$$m$$$ ($$$1 \le m \le n$$$) beautiful, if there exists two indices $$$l, r$$$ ($$$1 \le l \le r \le n$$$), such that the numbers $$$[p_l, p_{l+1}, \ldots, p_r]$$$ is a permutation of numbers $$$1, 2, \ldots, m$$$.

For example, let $$$p = [4, 5, 1, 3, 2, 6]$$$. In this case, the numbers $$$1, 3, 5, 6$$$ are beautiful and $$$2, 4$$$ are not. It is because:

- if $$$l = 3$$$ and $$$r = 3$$$ we will have a permutation $$$[1]$$$ for $$$m = 1$$$;
- if $$$l = 3$$$ and $$$r = 5$$$ we will have a permutation $$$[1, 3, 2]$$$ for $$$m = 3$$$;
- if $$$l = 1$$$ and $$$r = 5$$$ we will have a permutation $$$[4, 5, 1, 3, 2]$$$ for $$$m = 5$$$;
- if $$$l = 1$$$ and $$$r = 6$$$ we will have a permutation $$$[4, 5, 1, 3, 2, 6]$$$ for $$$m = 6$$$;
- it is impossible to take some $$$l$$$ and $$$r$$$, such that $$$[p_l, p_{l+1}, \ldots, p_r]$$$ is a permutation of numbers $$$1, 2, \ldots, m$$$ for $$$m = 2$$$ and for $$$m = 4$$$.

You are given a permutation $$$p=[p_1, p_2, \ldots, p_n]$$$. For all $$$m$$$ ($$$1 \le m \le n$$$) determine if it is a beautiful number or not.

Input

The first line contains the only integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. The next lines contain the description of test cases.

The first line of a test case contains a number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the given permutation $$$p$$$. The next line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are different) — the given permutation $$$p$$$.

It is guaranteed, that the sum of $$$n$$$ from all test cases in the input doesn't exceed $$$2 \cdot 10^5$$$.

Output

Print $$$t$$$ lines — the answers to test cases in the order they are given in the input.

The answer to a test case is the string of length $$$n$$$, there the $$$i$$$-th character is equal to $$$1$$$ if $$$i$$$ is a beautiful number and is equal to $$$0$$$ if $$$i$$$ is not a beautiful number.

Example

Input

3 6 4 5 1 3 2 6 5 5 3 1 2 4 4 1 4 3 2

Output

101011 11111 1001

Note

The first test case is described in the problem statement.

In the second test case all numbers from $$$1$$$ to $$$5$$$ are beautiful:

- if $$$l = 3$$$ and $$$r = 3$$$ we will have a permutation $$$[1]$$$ for $$$m = 1$$$;
- if $$$l = 3$$$ and $$$r = 4$$$ we will have a permutation $$$[1, 2]$$$ for $$$m = 2$$$;
- if $$$l = 2$$$ and $$$r = 4$$$ we will have a permutation $$$[3, 1, 2]$$$ for $$$m = 3$$$;
- if $$$l = 2$$$ and $$$r = 5$$$ we will have a permutation $$$[3, 1, 2, 4]$$$ for $$$m = 4$$$;
- if $$$l = 1$$$ and $$$r = 5$$$ we will have a permutation $$$[5, 3, 1, 2, 4]$$$ for $$$m = 5$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/17/2020 19:59:03 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|