시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB207660.000%

## 문제

There is a set of 2xN cubes. Each cube has an integer ranging from 1 to N assigned to it, labeling each of the cube's sides. Each number is written on exactly two cubes. Cubes are placed one on top of another, in a pile. If two cubes with the same number stand next to each other, they annihilate: both cubes disappear, and cubes standing above come down to fill the space. Your task is to disassemble the pile – eliminate all cubes. You are allowed to swap any two neighboring cubes. A swap could be done only after all possible annihilations are done.

For example, if N=4 and cubes are standing as you see on the right then you need to make one swap. Cubes with label 3 annihilate immediately; you swap the fourth bottom cube (with label 1) and the fifth bottom cube (with label 4); afterwards, cubes with labels 4 annihilate, followed by cubes with labels 1 and labels 2. Other option is to swap third and fourth bottom cubes (in this case cubes with labels 1 and 4 annihilate at same time, followed by cubes with label 2), or second and third.

If N=3, and cubes are standing like shown on the right, you need to perform 3 swaps. One way to solve is to swap fifth and sixth cubes, then fourth and fifth; cubes with labels 2 annihilate; then swap second and third; other cubes annihilate simultaneously. The task is to find the minimal number of swaps, such that all cubes are eliminated.

## 입력

The first line in the input file contains the positive integer N, 2<=N<=100000. The second line contains the labels of all cubes, bottom up, split by spaces.

## 출력

The only line in the output should contain one non-negative integer M – the minimal number of swaps necessary to destroy all cubes.

## 예제 입력 1

4
2 1 4 3 3 1 4 2


## 예제 출력 1

1


## 예제 입력 2

3
1 3 2 1 3 2


## 예제 출력 2

3


## 예제 입력 3

3
1 3 2 2 3 1


## 예제 출력 3

0