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