Луна обожнює побачення

Луна придумала шалену ідею. Вона вишикувала своїх $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$.