eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Мутація

Мутація

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Учені-генетики планети Олімпія знову проводять експерименти над ДНК примітивних організмів. Геном організму - це послідовність генів, кожний з яких можна закодувати одним натуральним числом. Гени, що кодуються одними і тими самими числами, вважаються однаковими, і навпаки, гени, що кодуються різними числами, вважаються різними.

Учені вже вивели деякий примітивний організм, якому вони хочуть модифікувати геном таким чином, щоб отримати ідеальний організм. Вони вважають, що у подальшому це допоможе знайти ліки від багатьох хвороб.

Організм вважається ідеальним, якщо будь-які два однакових гени або стоять на сусідніх позиціях у геномі, або між ними є хоча б один ген такий самий, як вони.

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

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

Вхідні дані

Перший рядок містить кількість генів n~(1 \le n \le 10^5) у геномі примітивного організму. У наступному рядку записано n натуральних чисел, кожне з яких не перевищує n — послідовність генів у геномі.

Вихідні дані

Виведіть найменшу кількість операцій, за яку вчені зможуть отримати ідеальний організм.

Приклад

Вхідні дані #1
9
1 2 1 3 1 3 2 4 5
Вихідні дані #1
2
Автор Ярослав Твердохліб
Джерело 2013 XXVI Всеукраинская олимпиада по информатике, Луганск, Март 17 - 21, тур 1