[POI2007]TET-Tetris Attack

题目描述

A puzzle called "Tetris Attack" has lately become a very popular game in Byteotia. The game itself is highlysophisticated, so we shall only introduce its simplified rules: the player is given a stack of $2n$ elements, placedone on another and marked with $n$ different symbols. Exactly two elements of the stack are marked with eachsymbol. A player's move consists in swapping two neighbouring elements, ie. interchanging them. If, as aresult of the swap, there are some two neighbouring elements marked with the same symbol, they are bothremoved from the stack. Then all the elements that have been above them fall down in consequence and mayvery well cause another removals. The player's goal is emptying the stack in the least possible number ofmoves. TaskWrite a programme that: reads the description of the initial stack content from the standard input, finds a solution with the minimum number of moves possible, writes out the outcome to the standard output. 给定一个长度为2n的序列,1~n各出现两次,可以交换相邻两项,两个同样的数放在一起会对消,求把所有数对消的最小交换次数。 # 温馨提示,输出方案。

输入输出格式

输入格式


In the first line of the standard input there is one integer $n$, $1\le n\le 50\ 000$. The following $2n$ lines describe theinitial content of the stack. The $(i+1)$'th line contains one integer $a_i$ -the symbol which the $i$'th ($1\le a_i\le n$)element from the bottom is marked with. Each symbol appears in the stack exactly twice. Moreover, notwo identical symbols neighbour initially. The test data is well chosen so that a solution with no more than $1\ 000\ 000$ moves exists.

输出格式


A solution with the minimum number of moves possible should be written out to the standard output asfollows. The first line should contain one integer $m$ -the minimum number of moves. The following $m$ should describe the optimal solution itself, i.e. a sequence of $m$ integers $p_1,\cdots,p_m$), one in each line. $p_i$ denotes that in $i$'th move the player has chosen to swap the $p_i$'thand $(p_i+1)$'th elements from the bottom. If more than one optimal solution exists, your programme should write out any one of them.

输入输出样例

输入样例 #1

5
5
2
3
1
4
1
4
3
5
2

输出样例 #1

2
5
2

说明

SPJ返回WA:Something Left为方案错误 # 温馨提示,输出方案。