e-olymp

Мутация

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

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

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

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

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

Входные данные

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

Выходные данные

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
9
1 2 1 3 1 3 2 4 5
Çıxış verilənləri #1
2
Müəllif Yaroslav Tverdohleb
Mənbə 2013 XXVI All-Ukrainian Informatics Olympiad, Lugansk, March 17 - 21, Round 1