406597: GYM102452 E Erasing Numbers

After a long statistics lecture, the students are about to leave the classroom when it suddenly starts to rain heavily. Since you don't have your umbrella with you, you decide to stay in the classroom and hope the rain will end soon. Several minutes later, you are the only person still left in the classroom. You realize something interesting: there are $$$N$$$ ($$$N$$$ is odd) distinct integers written in a line on the blackboard. Because you are very bored, you decide to erase those numbers from the blackboard so that the janitor will have less work to do.

Piece of chalk and blackboard. Public domain.

Since you have just learned the concepts of median during the lecture, you invented the following erase-operation for three integers: wipe off the largest number and the smallest number from the blackboard, so that only the median of the three numbers remains. You decide to repeat the following process: choose three consecutive integers on the blackboard and apply erase-operation on them. After this operation, the number of integers on the blackboard will decrease by $$$2$$$. Eventually, there will be only one integer left after this process is repeated $$$\frac{N-1}{2}$$$ times. Suddenly, you come up with an interesting question: which integers may survive until the end?

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \le T \le 1\,000)$$$, the number of cases.

For each case, the first line of the input contains a single integer $$$N$$$ ($$$1 \le N \le 5\,000$$$, $$$N$$$ is odd), the number of integers on the blackboard initially. The second line contains $$$N$$$ distinct integers $$$a_1, a_2, \dots, a_N \ (1 \le a_i \le N)$$$, where $$$a_i \ (1 \le i \le n)$$$ denotes the $$$i$$$-th integer on the blackboard.

It is guaranteed that the sum of $$$N$$$ over all cases doesn't exceed $$$10^4$$$.

For each case, print a string consisting of $$$N$$$ characters in a single line. The $$$i$$$-th $$$(1 \le i \le N)$$$ character of the string should be '1' if it is possible for $$$a_i$$$ to remain as the only integer in the end, otherwise it should be '0'.

2
5
3 1 2 5 4
3
2 3 1

10001
100