Картина 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 и десятую ячейку. Это не изменило бы финальное состояние.