Problems
Луна обожает свидание
Луна обожает свидание
Луна придумала безумную идею. Она выстроила своих $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$.
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