Сучасне мистецтво 3
Картина Пікассо може бути представлена одномірним масивом кольорів довжини n, де кожен колір позначається цілим числом в діапазоні від 1 до n.
Моне копіює таку картину наступним чином: він фарбує певний інтервал одним кольором, чекає, поки фарба висохне, потім фарбує інший інтервал і так далі. Моне може використовувати кожен з n кольорів стільки разів, скільки забажає (можливо, жодного разу).
Визначте мінімальну кількість рухів пензля одним кольором, необхідну Моне, щоб скопіювати картину Пікассо.
Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 300).
Другий рядок містить n цілих чисел у діапазоні 1..n, які вказують колір кожної комірки в картині Пікассо.
Вихідні дані
Виведіть мінімальну кількість рухів пензля, щоб скопіювати картину.
Приклад
У цьому прикладі Моне може скопіювати картину так: (ми позначаємо незабарвлені комірки кольором 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 і десяту комірку. Це не змінило б фінальний стан.