Beautiful Numbers
Contest: Codeforces Round 604 (Div. 2)
Difficulty rating: 1300
Tags: data structures, implementation, math, two pointers

You 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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

Example output:
101011
11111
1001

Editorial:
A number $$$m$$$ is beautiful if and only if all numbers in range $$$[1, m]$$$ occupies $$$m$$$ consecutive positions in the given sequence $$$p$$$. This is equivalent to $$$pos_{max} - pos_{min} + 1 = m$$$ where $$$pos_{max}, pos_{min}$$$ are the largest, smallest position of $$$1, 2, \dots, m$$$ in sequence $$$p$$$ respectively.
We will consider $$$m$$$ in increasing order, that its $$$m = 1, 2, \ldots, n$$$. For each $$$m$$$ we will find a way to update $$$pos_{max}, pos_{min}$$$ so we can tell either $$$m$$$ is a beautiful number or not in constant time. Denote $$$pos_i$$$ is the position of number $$$i$$$ in the sequence $$$p$$$. When $$$m=1$$$, we have $$$pos_{max} = pos_{min} = pos_1$$$. When $$$m>1$$$, the value of $$$pos_{max}, pos_{min}$$$ can be updated by the following formula:
• $$$new\_pos_{max} = max(old\_pos_{max}, pos_m)$$$
• $$$new\_pos_{min} = min(old\_pos_{min}, pos_m)$$$
Total time comlexity: $$$\mathcal{O}(n)$$$