Луна придумала безумную идею. Она выстроила своих 2n друзей в линию и дала каждому из них целое число от 1 до n включительно. Каждое число встречается ровно два раза. Каждая пара друзей, имеющих одинаковое число, образует пару.
Луна хочет отправить каждую из n пар на свидание. Однако это не так просто. Чтобы отправить пару на свидание, два друга, которые составляют пару, должны стоять рядом друг с другом в линии, то есть между ними не должен стоять кто-то другой.
Имеются два возможных действия, которые может осуществить Луна:
Она может поменять местами любых двух друзей, которые стоят рядом друг с другом в линии.
Если пара стоит рядом друг с другом в линии, то Луна может отправить их на свидание. Это удаляет пару с линии. Затем оставшиеся друзья заполняют освободившиеся места.
Действия можно выполнять в любом порядке. Например, Луна может поменять друзей местами, затем отправить несколько пар друзей на свидание, а потом снова менять друзей местами.
Найдите и выведите минимальное количество действий, необходимых для отправки всех друзей на свидание.
Первая строка содержит одно целое число n.
Вторая строка содержит 2n целых чисел ai (1≤ai≤n) — последовательность чисел у друзей.
Выведите одно целое число - минимальное количество действий, которое нужно сделать Луне чтобы отправить все пары на свидание.
В первом примере Луна может поменять местами третьего и четвертого друга. После этого линия будет выглядеть так: 3 1 1 2 2 3.
Затем она может отправить пару с номером 1 и пару с номером 2 на свидание (в любом порядке). Как только она это сделает, двое друзей с номером 3 теперь будут находиться рядом друг с другом в линии, и Луна может также отправить их на свидание.
В целом это решение выполняет 4 действия: один раз поменять местами и три раза отправить на свидание.
Блок 1 (7 балов): Для каждой пары нет другого человека, который находится между ними, а также 1≤n≤100.
Блок 2 (8 балов): Для каждой пары есть максимум один человек, который находится между ними, а также 1≤n≤100.
Блок 3 (11 балов): Первые n друзей в линии получили числа от 1 до n ровно один раз, но необязательно в отсортированном порядке. Более того, 1≤n≤3000.
Блок 4 (16 балов): Первые n друзей в линии получили числа от 1 до n ровно один раз, но необязательно в отсортированном порядке. Более того, 1≤n≤500000.
Блок 5 (22 балла): 1≤n≤3000.
Блок 6 (36 балов): 1≤n≤500000.