Современное искусство 3
Современное искусство 3
Картина Picowso может быть описана одномерным массивом цветов длины n, где каждый цвет указывается целым числом в интервале 1..n.
Moonet копирует такую картину следующим способом: красит некоторый интервал одним цветом, ждёт пока краска высохнет, затем красит другой интервал и т.д. Moonet может использовать каждый из n цветов столько раз, сколько пожелает (возможно ни одного).
Вычислите минимальное количество движений кисти одним цветом, которое потребуется Moonet, чтобы скопировать картину Picowso.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 300).
Следующая строка содержит n целых чисел в интервале 1..n, указывающих цвет каждой ячейки в картине Picowso.
Выходные данные
Выведите минимальное количество движений кисти, чтобы скопировать картину.
Пример
В этом примере, Moonet может скопироват картину так: (мы обозначаем незакрашенные ячейки цветом 0).
- Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
- Moonet закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
- Moonet закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
- Moonet закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
- Moonet закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
- Moonet закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
- Moonet закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.
10 1 2 3 4 1 4 3 2 1 6
6