P3460 [POI 2007] TET-Tetris Attack

A puzzle game named Tetris Attack is popular in Byteotia. The game itself is very complex, so we only describe its simplified rules: The player has a stack with $2n$ elements, one placed atop another. There are $n$ distinct symbols in total. For each symbol, exactly two elements in the stack are labeled with that symbol. The player may swap two adjacent elements, i.e., exchange their positions. After a swap, if two adjacent elements bear the same symbol, remove both from the stack. Then all elements above them fall down, which may trigger further removals. The goal is to empty the stack with the fewest moves. Write a program to find the minimum number of moves and one corresponding sequence of swaps.

The first line contains an integer $n$. The next $2n$ lines give the initial contents of the stack. The $(i+1)$-th line contains an integer $a_i$ ($1 \leq a_i \leq n$), indicating that the $i$-th element from the bottom is labeled with symbol $a_i$ (each symbol appears in the stack exactly twice). Initially, there are no two adjacent elements with the same symbol. It is guaranteed that there exists a solution with at most $10^6$ moves.

The first line contains an integer $m$, the minimum number of moves. The next $m$ lines each contain one number. On the $(i+1)$-th line, output $p_i$, meaning that on the $i$-th step the player swaps positions $p_i$ and $p_{i+1}$. If there are multiple valid solutions, output any of them.

$1 \le n \le 50000$. Translated by ChatGPT 5