Сучасне мистецтво 3#11214

Сучасне мистецтво 3

1 секунда

128 мегабайтів

Легка

Втомившись від стандартного $2$ -вимірного мистецтва (а також розчарувавшись через те, що інші копіюють її роботи), велика корова-художник Picowso вирішила перейти до більш мінімалістського $1$ -вимірного стилю. Її останню картину можна описати за допомогою $1$ -вимірного масиву кольорів довжини $n$ , де кожен колір заданий цілим числом у діапазоні від $1$ до $n$ .

На велике розчарування Picowso, її конкурент Moonet схоже теж навчився копіювати навіть ці $1$ -вимірні картини! Moonet фарбує один інтервал в один колір, чекає доки фарба висохне, потім фарбує інший інтервал і так далі. Moonet може використовувати кожен із $n$ кольорів стільки разів, скільки забажає (можливо, жодного разу).

Визначте, скільки мазків пензля потрібно Moonet, щоб скопіювати останню $1$ -вимірну картину Picowso.

Вхідні дані

Перший рядок містить $n$ ( $1 \leq n \leq 300$ 1 \leq n \leq 300).

Другий рядок містить $n$ цілих чисел у діапазоні $1.. n$ , що вказують колір кожної клітинки останньої $1$ -вимірної картини Picowso.

Вихідні дані

Виведіть мінімальну кількість мазків пензля, необхідних для копіювання картини.

Приклади

Приклад

10
1 2 3 4 1 4 3 2 1 6

Приклад 1

Примітка

У цьому прикладі Moonet може виконати фарбування наступним чином. Нефарбовану клітинку позначимо як $0$ .

- Спочатку весь масив не фарбований:

0000000000

0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0

- Moonet фарбує перші дев'ять клітинок кольором $1$ :

1111111110

1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 0

- Moonet фарбує інтервал кольором $2$ :

1222222210

1\ 2\ 2\ 2\ 2\ 2\ 2\ 2\ 1\ 0

- Moonet фарбує інтервал кольором $3$ :

1233333210

1\ 2\ 3\ 3\ 3\ 3\ 3\ 2\ 1\ 0

- Moonet фарбує інтервал кольором $4$ :

1234443210

1\ 2\ 3\ 4\ 4\ 4\ 3\ 2\ 1\ 0

- Moonet фарбує одну клітинку кольором $1$ :

1234143210

1\ 2\ 3\ 4\ 1\ 4\ 3\ 2\ 1\ 0

- Moonet фарбує останню клітинку кольором $6$ :

1234143216

1\ 2\ 3\ 4\ 1\ 4\ 3\ 2\ 1\ 6

Зверніть увагу, що під час першого мазка Moonet міг би пофарбувати десяту клітинку кольором $1$ разом із першими дев'ятьма клітинками, не вплинувши на фінальний стан масиву.