eolymp
Competitions

European Girls' Olympiad in Informatics 2021, I Day

Луна обожает свидание

Луна придумала безумную идею. Она выстроила своих $2n$ друзей в линию и дала каждому из них целое число от $1$ до $n$ включительно. Каждое число встречается ровно два раза. Каждая пара друзей, имеющих одинаковое число, образует пару. Луна хочет отправить каждую из $n$ пар на свидание. Однако это не так просто. Чтобы отправить пару на свидание, два друга, которые составляют пару, должны стоять рядом друг с другом в линии, то есть между ними не должен стоять кто-то другой. Имеются два возможных действия, которые может осуществить Луна: \begin{itemize} \item Она может поменять местами любых двух друзей, которые стоят рядом друг с другом в линии. \item Если пара стоит рядом друг с другом в линии, то Луна может отправить их на свидание. Это удаляет пару с линии. Затем оставшиеся друзья заполняют освободившиеся места. \end{itemize} Действия можно выполнять в любом порядке. Например, Луна может поменять друзей местами, затем отправить несколько пар друзей на свидание, а потом снова менять друзей местами. Найдите и выведите минимальное количество действий, необходимых для отправки всех друзей на свидание. \InputFile Первая строка содержит одно целое число $n$. Вторая строка содержит $2n$ целых чисел $a_i$ ($1 \leq a_i \leq n$) --- последовательность чисел у друзей. \OutputFile Выведите одно целое число - минимальное количество действий, которое нужно сделать Луне чтобы отправить все пары на свидание. \Note В первом примере Луна может поменять местами третьего и четвертого друга. После этого линия будет выглядеть так: 3 1 1 2 2 3. Затем она может отправить пару с номером 1 и пару с номером 2 на свидание (в любом порядке). Как только она это сделает, двое друзей с номером 3 теперь будут находиться рядом друг с другом в линии, и Луна может также отправить их на свидание. В целом это решение выполняет 4 действия: один раз поменять местами и три раза отправить на свидание. \Scoring Блок 1 (7 балов): Для каждой пары нет другого человека, который находится между ними, а также $1 \le n \le 100$. Блок 2 (8 балов): Для каждой пары есть максимум один человек, который находится между ними, а также $1 \le n \le 100$. Блок 3 (11 балов): Первые $n$ друзей в линии получили числа от $1$ до $n$ ровно один раз, но необязательно в отсортированном порядке. Более того, $1 \le n \le 3\,000$. Блок 4 (16 балов): Первые $n$ друзей в линии получили числа от $1$ до $n$ ровно один раз, но необязательно в отсортированном порядке. Более того, $1 \le n \le 500\,000$. Блок 5 (22 балла): $1 \le n \le 3\,000$. Блок 6 (36 балов): $1 \le n \le 500\,000$.
Time limit 1.5 second
Memory limit 256 MiB
Input example #1
3
3 1 2 1 2 3
Output example #1
4
Input example #2
5
5 1 2 3 2 3 1 4 5 4
Output example #2
7
Author Anton Tsypko