{"raw_statement":[{"iden":"problem statement","content":"You are given an integer sequence $X=(X_1,X_2,\\cdots,X_N)$ of length $N$ consisting of $0$ and $1$.\nYou can perform the following operation zero or more times:\n\n*   Classify each element of $X$ into group `A` or group `B`. Then, for each group, reverse the order of the elements it contains. More formally, if the elements contained in a group are $X_{i_1},X_{i_2},\\cdots,X_{i_s}$ ($i_1<i_2<\\cdots<i_s$), then for all $1 \\leq j \\leq s$, simultaneously replace the value of $X_{i_j}$ with $X_{i_{s+1-j}}$.\n\nYour goal is to make $X$ non-decreasing. Find the minimum number of operations needed to achieve the goal and the way to perform the operations. It can be proved that a solution always exists under the constraints of this problem.\nSolve $T$ cases for one input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 250000$\n*   $1 \\leq N \\leq 250000$\n*   $0 \\leq X_i \\leq 1$\n*   The sum of $N$ over the $T$ cases is at most $250000$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$X_1$ $X_2$ $\\cdots$ $X_N$"},{"iden":"sample input 1","content":"2\n4\n0 1 0 1\n5\n0 0 1 1 1"},{"iden":"sample output 1","content":"2\nAABA\nBBBB\n0\n\nFor the first test case, the goal can be achieved in two operations as follows, which is the minimum number of operations:\n\n*   First operation: Use $s_1$\\=`AABA`. Since $(X_1,X_2,X_4)$ are in group `A`, reverse their order, resulting in $(X_1,X_2,X_4)=(1,1,0)$. Similarly, since $(X_3)$ is in group `B`, reverse their order, resulting in $(X_3)=(0)$. Thus, overall we get $X=(1,1,0,0)$.\n    \n*   Second operation: Use $s_2$\\=`BBBB`. Since $()$ are in group `A`, reverse their order, resulting in $()=()$. Similarly, since $(X_1,X_2,X_3,X_4)$ are in group `B`, reverse their order, resulting in $(X_1,X_2,X_3,X_4)=(0,0,1,1)$. Thus, overall we get $X=(0,0,1,1)$.\n    \n\nFor the second test case, the goal can be achieved by performing the operation zero times."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}