Task
In preparation for the Fo()otball cup, the cheerleaders from Little Square’s school are trying to create a new routine. There are cheerleaders with distinct heights between and . The cheerleaders stand in a row. The height of the cheerleader that is initially at position is for .
The cheerleaders know two coordinate dance moves:
- The big swap. In this move, the first cheerleaders swap places with the last 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 elements has the following effect:
And a big split on elements has the following effect:
Now, define the number of inversions of a row of cheerleaders with heights as the number of pairs , where . 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 . On the second line of the input you will find integers, that represent .
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 represents a big swap, and a represents a big split. Any sequence of moves that leads to the minimum number of inversions will be accepted.
Constraints and clarifications
- .
- can be .
- If you output the correct minimum number of inversions, but the string of moves is incorrect, you will receive points. The value of varies from subtask to subtask.
- The length of the string of moves must be at most characters long.
# | Points | Restrictions |
---|---|---|
1 | 16 | , |
2 | 10 | , |
3 | 25 | , |
4 | 21 | , . It is guaranteed that the minimum number of inversions that can be achieved is . |
5 | 28 | . No additional restrictions. |
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