T533508 「GFOI Round 2」Colors (English ver.)

**[Chinese statement](https://www.luogu.com.cn/problem/P11282). You must submit your code at the Chinese version of the statement.** > 世界が鮮やかに 染まって

There are $n$ balls arranged in a row, numbered from $1$ to $n$ from left to right. Initially, each ball is red. The initial weight of the $i$-th ball is $p_i$. **It is guaranteed that $\bm{n}$ is an odd number and that $\bm{p}$ is a permutation of $\bm{1 \sim n}$.** You need to perform exactly $\frac{n - 1}{2}$ operations. In one operation, you must: - Choose a **red** ball $i$ such that there is at least one red ball in the range $1 \sim i - 1$ and at least one red ball in the range $i + 1 \sim n$. - Let $j$ be the largest integer such that $j < i$ and the ball at position $j$ is red, and let $k$ be the smallest integer such that $k > i$ and the ball at position $k$ is red. You will paint both balls $i$ and $k$ blue. - Then, perform exactly one of the following two operations: - Modify $p_j$ (the weight of ball $j$) to $\max(p_i, p_j, p_k)$; - Modify $p_j$ (the weight of ball $j$) to $\min(p_i, p_j, p_k)$. After performing $\frac{n - 1}{2}$ operations, there will be exactly one red ball left. You need to determine for each positive integer $x$ in the range $1$ to $n$ whether it is possible to perform the operations in such a way that the weight of the remaining red ball is $x$.

无

无

#### Sample Explanation For the first test case, the initial state of the balls (color and weight) is $\color{red}{3\ 2\ 1}$. You need to perform $1$ operation. In this operation, you can only choose ball $2$ and paint both balls $2$ and $3$ blue. - If you choose to modify $p_1$ to $\max(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{3}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $3$; - If you choose to modify $p_1$ to $\min(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{1}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $1$. Thus, you will output a $01$ string that has $1$s at the $1$st and $3$rd positions, and $0$s in the other positions. For the second test case, it can be easily proven that the weight of the remaining red ball can take all positive integers from $1$ to $n$. Here is an example of a sequence of operations that results in the remaining red ball having a weight of $2$: - The initial state of the balls is $\color{red}{1\ 3\ 5\ 2\ 4}$. - Choose ball $2$, paint both balls $2$ and $3$ blue, and set $p_1$ to $\max(p_1, p_2, p_3) = 5$. After this operation, the state of the balls becomes $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$. - Choose ball $4$, paint both balls $4$ and $5$ blue, and set $p_1$ to $\min(p_1, p_4, p_5) = 2$. After this operation, the state of the balls becomes $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$. #### Subtasks and Constraints | Subtask ID | $n \le$ | $\sum n \le$ | Special Properties | Score | | :-: | :-: | :-: | :-: | :-: | | $1$ | $5$ | $10^4$ | No | $16$ | | $2$ | $19$ | $10^4$ | No | $19$ | | $3$ | $99$ | $10^6$ | No | $19$ | | $4$ | $10^6 - 1$ | $10^6$ | A | $3$ | | $5$ | $10^6 - 1$ | $10^6$ | No | $43$ | - Special Property A: $p_i = i$. For all tests, it is guaranteed that: - $1 \le T \le 10^5$; - $3 \le n \le 10^6 - 1$ and $n$ is an odd number; - $\sum n \le 10^6$; - $p$ is a permutation of $1 \sim n$.