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