e-olymp

Мутація

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

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

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

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

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

Вхідні дані

Перший рядок містить кількість генів n (1n105) у геномі примітивного організму. У наступному рядку записано n натуральних чисел, кожне з яких не перевищує n - послідовність генів у геномі.

Вихідні дані

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

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