Background

Day 1 Problem B.

The statement is translated from EGOI2021 luna.

Problem Description

Luna came up with an unusual idea. She lines up $2n$ friends in a long queue and gives each of them an integer from $1 \sim n$. Each integer appears exactly twice. Each pair of friends with the same number forms a couple.

Luna wants every couple to go on a date once. However, it is not that simple. For a couple to go on a date, the two people must stand next to each other in the queue, meaning there cannot be anyone between them.

Luna can perform two types of operations:

• She can swap any two adjacent people.
• If a couple is adjacent, Luna can let them go on a date. This couple will leave the queue, and the people behind them will move forward to fill their positions.

All operations can be performed in any order. For example, she can swap several times, then let some couples go on dates, then swap again.

Find the minimum number of operations needed to let everyone go on a date.

Input Format

The first line contains an integer $n$.

The second line contains $2n$ integers $a_i$, in order, representing the numbers held by the friends in the queue.

Output Format

Print one line with one integer, the minimum number of operations.

3
3 1 2 1 2 3

4

5
5 1 2 3 2 3 1 4 5 4

7

Hint

Explanation for Sample $1$

Luna first swaps the third person and the fourth person, obtaining $3,1,1,2,2,3$.

Then she can let the couples with numbers $1$ and $2$ go on dates. After that, the couple with number $3$ will become adjacent, and Luna can also let them go on a date.

In total, $4$ operations are needed: one swap and three operations of letting a couple go on a date.

Constraints

For all testdata, $1 \le n \le 5 \times 10^5$, $1 \le a_i \le n$.

• Subtask 1 ($7$ points): every couple is adjacent, $n \le 100$.
• Subtask 2 ($8$ points): between the two people of any couple, there is at most one person, $n \le 100$.
• Subtask 3 ($11$ points): the numbers of the first $n$ people form a permutation of $1 \sim n$, $n \le 3 \times 10^3$.
• Subtask 4 ($16$ points): the numbers of the first $n$ people form a permutation of $1 \sim n$.
• Subtask 5 ($22$ points): $n \le 3 \times 10^3$.
• Subtask 6 ($36$ points): no special restrictions.

Translated by ChatGPT 5