Rating Compression
Contest: Codeforces Global Round 12
Difficulty rating: 1800
Tags: binary search, data structures, greedy, implementation, two pointers

On the competitive programming platform CodeCook, every person has a rating graph described by an array of integers $$$a$$$ of length $$$n$$$. You are now updating the infrastructure, so you've created a program to compress these graphs.

The program works as follows. Given an integer parameter $$$k$$$, the program takes the minimum of each contiguous subarray of length $$$k$$$ in $$$a$$$.

More formally, for an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$, define the $$$k$$$-compression array of $$$a$$$ as an array $$$b$$$ of length $$$n-k+1$$$, such that $$$$$$b_j =\min_{j\le i\le j+k-1}a_i$$$$$$

For example, the $$$3$$$-compression array of $$$[1, 3, 4, 5, 2]$$$ is $$$[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}]=[1, 3, 2].$$$

A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$m=3$$$ but there is $$$4$$$ in the array).

A $$$k$$$-compression array will make CodeCook users happy if it will be a permutation. Given an array $$$a$$$, determine for all $$$1\leq k\leq n$$$ if CodeCook users will be happy after a $$$k$$$-compression of this array or not.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$) — the number of test cases.

The first line of the description of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 3\cdot 10^5$$$) — the length of the array.

The second line of the description of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — the elements of the array.

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

Output format:
For each test case, print a binary string of length $$$n$$$.

The $$$k$$$-th character of the string should be $$$1$$$ if CodeCook users will be happy after a $$$k$$$-compression of the array $$$a$$$, and $$$0$$$ otherwise.

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

Note:
In the first test case, $$$a=[1, 5, 3, 4, 2]$$$.

- The $$$1$$$-compression of $$$a$$$ is $$$[1, 5, 3, 4, 2]$$$ and it is a permutation.
- The $$$2$$$-compression of $$$a$$$ is $$$[1, 3, 3, 2]$$$ and it is not a permutation, since $$$3$$$ appears twice.
- The $$$3$$$-compression of $$$a$$$ is $$$[1, 3, 2]$$$ and it is a permutation.
- The $$$4$$$-compression of $$$a$$$ is $$$[1, 2]$$$ and it is a permutation.
- The $$$5$$$-compression of $$$a$$$ is $$$[1]$$$ and it is a permutation.

Example input:
5
5
1 5 3 4 2
4
1 3 2 1
5
1 3 3 3 2
10
1 2 3 4 5 6 7 8 9 10
3
3 3 2

Example output:
10111
0001
00111
1111111111
000

Editorial:
For $$$k=1$$$, we simply need to check that the array is a permutation.
If $$$k=n$$$, we simply need to check that the array has minimum $$$1$$$.
For $$$1<k<n$$$, we know the $$$k$$$-compression should contain exactly one occurrence of $$$1$$$. But $$$1$$$ is the minimum possible element, so it should occur in only one length $$$k$$$ subarray. Therefore, $$$1$$$ should only occur at one of the extremes: index $$$1$$$ or index $$$n$$$. Without loss of generality, suppose it occurs at index $$$n$$$. Then we require that the $$$k$$$-compression of $$$a[1,\ldots,n-1]$$$ is a permutation of the numbers $$$\{2,3,\ldots,n-k+1\}$$$, and we can solve iteratively.
This gives us the following algorithm. We maintain an interval $$$[l,r]$$$. Initially $$$l=1$$$ and $$$r=n$$$. Now, we iterate $$$i=1,\ldots,n$$$. For each $$$i$$$, we make sure that either $$$a_l=i$$$ or $$$a_r=i$$$, increment $$$l$$$ or decrement $$$r$$$ accordingly. Then check that $$$\min\limits_{j=l}^r a_j=i+1$$$.
If $$$i$$$ is the first index that our checks fail, then the answer is $$$0$$$ for $$$2\le k\le n-i+1$$$ and the answer is $$$1$$$ for $$$n-i+1< k\le n$$$.
Checking the minimum element each iteration can be done with data structures like a sparse table or segment tree. It is also sufficient to maintain a $$$count$$$ array of the elements, for a complexity of $$$O(n)$$$.