Наскучившись стандартными двумерными произведениями искусства (а также разочаровавшись тем, что другие копируют ее работы), великая художница Пикоусо решила перейти к более минималистичному, одномерному стилю. Ее последняя картина может быть описана одномерным массивом цветов длины
N (
\(1<=N<=300\)), где каждый цвет указывается целым числом в интервале
\(1…N\).
К великому разочарованию Пикоусо, ее конкурент Муне, похоже, придумал, как копировать даже эти одномерные картины! Муне закрашивает один интервал одним цветом, ждет, пока он высохнет, затем красит другой интервал и так далее. Муне может использовать каждый из
N цветов столько раз, сколько пожелает (возможно ни одного).
Вычислите минимальное количество движений кисти одним цветом, которое потребуется Муне, чтобы скопировать картину Пикоусо.
Входные данные
Первая строка содержит число
N. Следующая строка содержит
N целых чисел в интервале
\(1…N\), указывающих цвет каждой ячейки в картине Пикоусо.
Выходные данные
Выведите минимальное количество движений кисти, чтобы скопировать картину.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10
1 2 3 4 1 4 3 2 1 6 |
6 |
Пояснение
В этом примере Муне может скопироват картину так: (незакрашенные ячейки обозначены цветом 0).
Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
Муне закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
Муне закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
Муне закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
Муне закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
Муне закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
Муне закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.