P9741 "KDOI-06-J" Reversal and Flip

Little W has a $01$ sequence $a_1,a_2,\ldots,a_n$ of length $n$. He will perform $n$ operations on this sequence in order. In the $i$-th operation ($1\le i\le n$), Little W will perform the following **two** transformations in order: 1. Reverse the numbers in the interval $[1,i]$ by index. Formally, after this transformation, the sequence $a$ becomes $a_i,a_{i-1},\ldots,a_{1},a_{i+1},a_{i+2},\ldots,a_n$. 2. Flip the numbers in the interval $[1,i]$ by value. Formally, after this transformation, for any $1\le j\le i$, if $a_j=0$ then $a_j$ becomes $1$, otherwise $a_j$ becomes $0$. Little W wants to know the value of each element in the sequence $a$ after all $n$ operations are finished.

Read input from standard input. The first line contains a positive integer $n$, representing the length of the sequence. The next line contains $n$ integers, representing the sequence $a_1,a_2,\ldots, a_n$. It is guaranteed that $a_i=0$ or $1$.

Write output to standard output. Output one line with $n$ integers, representing the value of each element in the sequence $a$ after all operations.

**[Sample Explanation #1]** The changes of sequence $a$ are shown in the table below: | Operation count | Changes of sequence $a$ | | :--: | :--: | | $1$ | $[1,1,1]\to [1,1,1]\to[0,1,1]$ | | $2$ | $[0,1,1]\to [1,0,1]\to[0,1,1]$ | | $3$ | $[0,1,1]\to [1,1,0]\to[0,0,1]$ | **[Sample Explanation #2]** The changes of sequence $a$ are shown in the table below: | Operation count | Sequence $a$ after the operation | | :--: | :--: | | - | $[1,0,1,1,1,0,0,1]$ | | $1$ | $[0,0,1,1,1,0,0,1]$ | | $2$ | $[1,1,1,1,1,0,0,1]$ | | $3$ | $[0,0,0,1,1,0,0,1]$ | | $4$ | $[0,1,1,1,1,0,0,1]$ | | $5$ | $[0,0,0,0,1,0,0,1]$ | | $6$ | $[1,0,1,1,1,1,0,1]$ | | $7$ | $[1,0,0,0,0,1,0,1]$ | | $8$ | $[0,1,0,1,1,1,1,0]$ | **[Sample #3]** See `revflip/revflip3.in` and `revflip/revflip3.ans` in the contestant files. **[Sample #4]** See `revflip/revflip4.in` and `revflip/revflip4.ans` in the contestant files. **[Constraints]** For all data, it is guaranteed that $1\le n\le 2\times 10^6$, and for any $1\le i\le n$, $a_i=0$ or $1$. | Test point ID | $n\le$ | Special property | | :-----------: | :-----------: | :----------: | | $1\sim 3$ | $10^3$ | None | | $4\sim 5$ | $10^5$ | None | | $6 \sim 7$ | $2\times 10^6$ | $a_i=0$ | | $8\sim 10$ | $2\times 10^6$ | None | Translated by ChatGPT 5