The Moon loves dates

The Moon has devised an intriguing plan. She arranged her $2n$ friends in a line and assigned each of them an integer from $1$ to $n$. Each number appears exactly twice, forming pairs of friends with the same number.

The Moon's goal is to send each of these $n$ pairs on a date. However, there's a catch: for a pair to go on a date, the two friends must be standing next to each other in the line, with no one else between them.

The Moon can perform two types of actions:

• Swap any two adjacent friends in the line.

• If a pair is standing next to each other, she can send them on a date, removing them from the line. The remaining friends then close the gap.

These actions can be performed in any sequence. For instance, she might swap friends, send several pairs on dates, and then swap again.

Your task is to determine the minimum number of actions required to send all pairs on dates.

Input

The first line contains a single integer $n$.

The second line contains $2n$ integers $a_i$ ($1\le a_i\le n$), representing the sequence of numbers assigned to the friends in their current order.

Output

Output a single integer — the minimum number of actions the Moon needs to perform to send all pairs on dates.

Examples

Note

In the first example, the Moon can swap the third and fourth friends. After this swap, the line will be: 3 1 1 2 2 3.

Then, she can send the pair with number 1 and the pair with number 2 on dates (in any order). After these pairs are sent on dates, the two friends with number 3 will be adjacent, allowing the Moon to send them on a date as well.

In total, this solution requires 4 actions: one swap and three dates.

Scoring

Block 1 (7 points): Each pair is already adjacent, and $1\le n\le 100$.

Block 2 (8 points): Each pair has at most one person between them, and $1\le n\le 100$.

Block 3 (11 points): The first $n$ friends have numbers from $1$ to $n$ exactly once, but not necessarily in order. Moreover, $1\le n\le 3,000$.

Block 4 (16 points): The first $n$ friends have numbers from $1$ to $n$ exactly once, but not necessarily in order. Moreover, $1\le n\le 500,000$.

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

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