Tetris Attack

Time limit1sMemory limit128 MB

Summary

A stack holds each of n symbols twice; adjacent equal pairs vanish on contact, and one move swaps neighboring elements. Find the minimum swaps to empty the stack.

Level: Hard8 of 10
Topics: Greedy, Stack, Simulation, Combinatorics
Solved: No attempts yet

Problem

The puzzle "Tetris Attack" has recently become very popular in Byteotia. The full game is quite elaborate, so here we describe only a simplified version.

A stack is built from $2n$ elements placed one on top of another. Each element carries one of $n$ symbols, and every symbol is written on exactly two elements.

A single move swaps two neighbouring elements, exchanging their positions. If, after a swap, two neighbouring elements carry the same symbol, both of them are removed from the stack. Every element that was above the removed pair falls down, and this may trigger further removals in a chain reaction.

The goal is to empty the stack completely in as few moves as possible. Given the initial contents of the stack, compute the minimum number of moves needed to empty it.

Input

The first line contains one integer $n$ ( $1 \le n \le 50{,}000$ ). The next $2n$ lines describe the initial stack from bottom to top. The $i$ -th of these lines contains the symbol $a_i$ written on the $i$ -th element from the bottom ( $1 \le a_i \le n$ ).

Every symbol appears exactly twice, and initially no two identical symbols are neighbours. The input is always chosen so that the stack can be emptied in at most $1{,}000{,}000$ moves.

Output

Print a single integer: the minimum number of moves needed to empty the stack.

Hint

Tetris Attack gameplay animation

Examples5

Example 1
Input
```
5
5
2
3
1
4
1
4
3
5
2
```
Expected output
```
2
```
Example 2
Input
```
2
1
2
1
2
```
Expected output
```
1
```
Example 3
Input
```
2
2
1
2
1
```
Expected output
```
1
```
Example 4
Input
```
3
1
2
3
1
2
3
```
Expected output
```
3
```
Example 5
Input
```
3
1
2
3
2
1
3
```
Expected output
```
2
```