Clearing the Tetris Attack Stack

Tetris Attack is a popular puzzle game in Byteotia. In its simplified version, you are given a stack with 2n elements. The stack is arranged such that each element is placed directly on top of another, and there are n distinct symbols in total. For every symbol, exactly two elements in the stack are labeled with that symbol.

You are allowed to swap two adjacent elements (i.e. exchange their positions). After a swap, if there exist two consecutive elements with the same symbol, both will be removed from the stack. Then, all the elements above will fall down, which might result in additional removals. This removal process is repeated as long as there exists a pair of adjacent elements with the same symbol.

Your goal is to clear the entire stack with the minimum number of swaps. You need to output the minimum number of moves, followed by a valid sequence of swap operations that achieves this result. In the output, each move is represented by the 1-indexed position of the lower element in the adjacent pair that is swapped.

The removal mechanism can be described mathematically as follows. Let \(S = s_1s_2\cdots s_{2n}\) be the sequence representing the stack from bottom to top. After any operation, apply the following elimination procedure repeatedly:

[ \text{while } \exists i \text{ such that } s_i = s_{i+1}, \text{ remove } s_i \text{ and } s_{i+1}, \text{ and let the above part fall down.} ]

inputFormat

The first line contains a single integer n (representing that there are 2n elements in the stack).

The second line contains a string of length 2n consisting of uppercase letters. Each letter represents the symbol of an element in the stack, given from bottom to top.

outputFormat

Output the minimum number of swaps required to clear the stack on the first line.

If the number of moves is greater than 0, output a second line containing the sequence of moves. Each move is represented by a number (1-indexed) indicating the position of the lower element in the adjacent pair that is swapped.

If no moves are required (i.e. the stack is initially cleared by the elimination procedure), output 0 and an empty second line.

sample

1
AA

0