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

Луна придумала безумную идею. Она выстроила своих $2n$ друзей в линию и дала каждому из них целое число от $1$ до $n$ включительно. Каждое число встречается ровно два раза. Каждая пара друзей, имеющих одинаковое число, образует пару.

Луна хочет отправить каждую из $n$ пар на свидание. Однако это не так просто. Чтобы отправить пару на свидание, два друга, которые составляют пару, должны стоять рядом друг с другом в линии, то есть между ними не должен стоять кто-то другой.

Имеются два возможных действия, которые может осуществить Луна:

• Она может поменять местами любых двух друзей, которые стоят рядом друг с другом в линии.

• Если пара стоит рядом друг с другом в линии, то Луна может отправить их на свидание. Это удаляет пару с линии. Затем оставшиеся друзья заполняют освободившиеся места.

Действия можно выполнять в любом порядке. Например, Луна может поменять друзей местами, затем отправить несколько пар друзей на свидание, а потом снова менять друзей местами.

Найдите и выведите минимальное количество действий, необходимых для отправки всех друзей на свидание.

Входные данные

Первая строка содержит одно целое число $n$.

Вторая строка содержит $2n$ целых чисел $a_i$ ($1\le a_i\le n$) — последовательность чисел у друзей.

Выходные данные

Выведите одно целое число - минимальное количество действий, которое нужно сделать Луне чтобы отправить все пары на свидание.

Примеры

Примечание

В первом примере Луна может поменять местами третьего и четвертого друга. После этого линия будет выглядеть так: 3 1 1 2 2 3.

Затем она может отправить пару с номером 1 и пару с номером 2 на свидание (в любом порядке). Как только она это сделает, двое друзей с номером 3 теперь будут находиться рядом друг с другом в линии, и Луна может также отправить их на свидание.

В целом это решение выполняет 4 действия: один раз поменять местами и три раза отправить на свидание.

Оценивание

Блок 1 (7 балов): Для каждой пары нет другого человека, который находится между ними, а также $1\le n\le 100$.

Блок 2 (8 балов): Для каждой пары есть максимум один человек, который находится между ними, а также $1\le n\le 100$.

Блок 3 (11 балов): Первые $n$ друзей в линии получили числа от $1$ до $n$ ровно один раз, но необязательно в отсортированном порядке. Более того, $1\le n\le 3000$.

Блок 4 (16 балов): Первые $n$ друзей в линии получили числа от $1$ до $n$ ровно один раз, но необязательно в отсортированном порядке. Более того, $1\le n\le 500000$.

Блок 5 (22 балла): $1\le n\le 3000$.

Блок 6 (36 балов): $1\le n\le 500000$.