EGOI '21 P2 - Luna Likes Love - DMOJ: Modern Online Judge

EGOI '21 P2 - Luna Likes Love

Points: 12 (partial)

Time limit: 1.5s

Memory limit: 256M

Problem type

European Girls' Olympiad in Informatics: 2021 Day 1 Problem 2

Luna came up with a wild idea. She lined up her $2n$ ~2n~ friends into a long line and gave each of them an integer number between $1$ ~1~ and $n$ ~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$ ~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.

Input Specification

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

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

Output Specification

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.

Constraints

Subtask	Points	Constraints
$1$ ~1~	$7$ ~7~	For each couple there is no person between the two friends forming a couple, and $1 \le n \le 100$ ~1 \le n \le 100~.
$2$ ~2~	$8$ ~8~	For each couple there is at most one person between the two friends forming a couple, and $1 \le n \le 100$ ~1 \le n \le 100~.
$3$ ~3~	$11$ ~11~	The first $n$ ~n~ friends in the line received integers from $1$ ~1~ to $n$ ~n~, each exactly once, not necessarily in order. Furthermore, $1 \le n \le 3\,000$ ~1 \le n \le 3\,000~.
$4$ ~4~	$16$ ~16~	The first $n$ ~n~ friends in the line received integers from $1$ ~1~ to $n$ ~n~, each exactly once, not necessarily in order. Furthermore, $1 \le n \le 500\,000$ ~1 \le n \le 500\,000~.
$5$ ~5~	$22$ ~22~	$1 \le n \le 3\,000$ ~1 \le n \le 3\,000~
$6$ ~6~	$36$ ~36~	$1 \le n \le 500\,000$ ~1 \le n \le 500\,000~

Sample Input 1

3
3 1 2 1 2 3

Sample Output 1

Explanation for Sample Output 1

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$ ~3, 1, 1, 2, 2, 3~.

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

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

Sample Input 2

5
5 1 2 3 2 3 1 4 5 4

Sample Output 2

Comments

There are no comments at the moment.