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

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

1,5 секунди

256 мегабайтів

Легка

Луна придумала шалену ідею. Вона вишикувала своїх $2 n$ друзів у лінію і дала кожному з них ціле число від $1$ до $n$ включно. Кожне число зустрічається рівно двічі. Кожна пара друзів, що мають однакове число, утворює пару.

Луна хоче відправити кожну з $n$ пар на побачення. Однак це не так просто. Щоб відправити пару на побачення, двоє друзів, що складають пару, повинні стояти поруч один з одним у лінії, тобто між ними не повинен стояти хтось інший.

Є дві можливі дії, які може здійснити Луна:

Вона може поміняти місцями будь-яких двох друзів, які стоять поруч один з одним у лінії.
Якщо пара стоїть поруч один з одним у лінії, Луна може відправити їх на побачення. Це видаляє пару з лінії. Потім друзі, що залишилися, заповнюють звільнені місця.

Дії можна виконувати в будь-якому порядку. Наприклад, вона може поміняти друзів місцями, потім відправити кілька пар друзів на побачення, а потім знову міняти місцями.

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

Вхідні дані

Перший рядок містить одне ціле число $n$ .

Другий рядок містить $2 n$ цілих чисел $a_{i}$ a_i ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — послідовність чисел у друзів.

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі Луна може поміняти місцями третього та четвертого друга. Після цього лінія виглядатиме так: $3$ $1$ $1$ $2$ $2$ $3$ .

Потім вона може відправити пару з номером $1$ та пару з номером $2$ на побачення (у будь-якому порядку). Як тільки вона це зробить, двоє друзів з номером $3$ тепер будуть знаходитися поруч один з одним у лінії, і Луна може також відправити їх на побачення.

Загалом це рішення виконує $4$ дії: один раз поміняти місцями та три рази відправити на побачення.

Оцінювання

Блок 1 (7 балів): Для кожної пари немає іншої людини, яка знаходиться між ними, а також $1 \leq n \leq 100$ 1 \le n \le 100.

Блок 2 (8 балів): Для кожної пари є максимум одна людина, яка знаходиться між ними, а також $1 \leq n \leq 100$ 1 \le n \le 100.

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

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

Блок 5 (22 бали): $1 \leq n \leq 3000$ 1 \le n \le 3\,000.

Блок 6 (36 балів): $1 \leq n \leq 500000$ 1 \le n \le 500\,000.