408480: GYM103148 B Luna Likes Love

Luna came up with a wild idea. She lined up her $$$2n$$$ friends into a long line and gave each of them an integer number between $$$1$$$ and $$$n$$$, inclusive. Each number is used exactly twice. Each pair of friends who share the same number forms a couple.

Luna wants to send each of the $$$n$$$ couples on a date. However, it is not that straightforward. In order to send a couple on a date, the two friends forming the couple must stand next to each other in the line, i.e., there cannot be anybody else standing between them.

There are two possible actions that Luna can take:

• She can swap any two friends who stand next to each other in the line.
• If a couple is standing next to each other in the line, Luna can send them on a date. This removes the couple from the line. The remaining friends then shift to fill in the gap in the line.

The actions can be performed in any order. E.g., she can make some swaps, then send some pairs of friends on a date, and then go back to making swaps.

Find and report the minimum number of actions needed to send everybody on a date.

The first line of the input contains a single integer $$$n$$$.

The second line of the input contains $$$2n$$$ single-space separated integers $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) – the sequence of numbers received by the friends in the long line, in order.

The first and only line of the output contains the minimum number of actions Luna must make in order to send every couple on a date.

Subtask 1 (7 points): For each couple there is no person between the two friends forming a couple, and $$$1 \le n \le 100$$$.

Subtask 2 (8 points): For each couple there is at most one person between the two friends forming a couple, and $$$1 \le n \le 100$$$.

Subtask 3 (11 points): The first $$$n$$$ friends in the line received integers from $$$1$$$ to $$$n$$$, each exactly once, not necessarily in order. Furthermore, $$$1 \le n \le 3\,000$$$.

Subtask 4 (16 points): The first $$$n$$$ friends in the line received integers from $$$1$$$ to $$$n$$$, each exactly once, not necessarily in order. Furthermore, $$$1 \le n \le 500\,000$$$.

Subtask 5 (22 points): $$$1 \le n \le 3\,000$$$.

Subtask 6 (36 points): $$$1 \le n \le 500\,000$$$.

3
3 1 2 1 2 3

4

5
5 1 2 3 2 3 1 4 5 4

7

In the first sample, Luna could start by swapping the third and the fourth friend. After this swap the line looks as follows: 3 1 1 2 2 3.

Then, she can send the couple with number 1 and the couple with number 2 on a date (in any order). Once she does so, the two friends with number 3 are now adjacent in line and Luna can send them on a date, too.

Overall this solution takes 4 actions: one swap and three dates.