Cheerleader

Task

In preparation for the Fo($1$)otball cup, the cheerleaders from Little Square’s school are trying to create a new routine. There are $2^N$ cheerleaders with distinct heights between $0$ and $2^N − 1$. The cheerleaders stand in a row. The height of the cheerleader that is initially at position $i$ is $h[i]$ for $1 \leq i \leq 2^N$.

The cheerleaders know two coordinate dance moves:

• The big swap. In this move, the first $2^{N−1}$ cheerleaders swap places with the last $2^{N−1}$ cheerleaders.
• The big split. In this move, the cheerleaders at odd positions go to the beginning of the row, and the cheerleaders at even positions go to the end of the row.

For instance, a big swap on $8$ elements has the following effect:

And a big split on $8$ elements has the following effect:

Now, define the number of inversions of a row of cheerleaders with heights $h'[1],\ \ldots,\ h'[2^N]$ as the number of pairs $(i, j)$, $1 \leq i < j \leq 2^N$ where $h'[i] > h'[j]$. The cheerleaders want to know a sequence of dance
moves that minimises the number of inversions in the resulting row.

Input data

On the first line of the input you will find $N$. On the second line of the input you will find $2^N$ integers, that represent $h[1],\ \ldots,\ h[2^N]$.

Output data

On the first line of the output, print the minimum number of inversions that can be achieved. On the
second line of the output, write a string that represents a sequence of dance moves that leads to that minimum number of inversions. In this string, a $1$ represents a big swap, and a $2$ represents a big split. Any sequence of moves that leads to the minimum number of inversions will be accepted.

Constraints and clarifications

• $0 \leq N \leq 17$.
• $N$ can be $0$.
• If you output the correct minimum number of inversions, but the string of moves is incorrect, you will receive $X$ points. The value of $X$ varies from subtask to subtask.
• The length of the string of moves must be at most $500 \ 000$ characters long.

Example 1

stdin

2
0 3 1 2

stdout

1
2212

Example 2

stdin

3
2 3 7 6 1 4 5 0

stdout

8
21221

Example 3

stdin

4
1 4 8 5 3 6 12 13 10 11 2 9 14 0 15 7

stdout

43
2222