Modern Art 3

시간 제한1초메모리 제한512 MB

요약

길이 N인 1차원 그림이 주어질 때, 한 번에 한 구간을 한 색으로 칠하는 붓질을 최소 몇 번 해야 그림을 그대로 재현할 수 있는지 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 구간, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

평범한 2차원 그림에 질린 데다 다른 소들이 자기 작품을 베끼는 것에까지 짜증이 난 위대한 소 화가 Picowso는 더 단순한 1차원 화풍으로 전환하기로 했다. Picowso의 최신작은 길이 $N$ ( $1 \leq N \leq 300$ )인 1차원 색 배열로 나타낼 수 있으며, 각 색은 $1\ldots N$ 범위의 정수로 주어진다.

Picowso를 몹시 낙담하게도, 경쟁자 Moonet은 이런 1차원 그림까지 베끼는 방법을 알아낸 모양이다. Moonet은 하나의 구간을 한 가지 색으로 칠하고, 마를 때까지 기다린 다음, 또 다른 구간을 칠하는 식으로 작업한다. Moonet은 $N$ 가지 색을 각각 원하는 만큼(전혀 쓰지 않아도 된다) 사용할 수 있다.

Moonet이 Picowso의 최신 1차원 그림을 베끼는 데 필요한 붓질 횟수를 구하시오.

입력

첫째 줄에 $N$ 이 주어진다.

다음 줄에 Picowso의 최신 1차원 그림에서 각 칸의 색을 나타내는 $N$ 개의 정수가 $1 \ldots N$ 범위로 주어진다.

출력

그림을 베끼는 데 필요한 최소 붓질 횟수를 출력한다.

예제1

예제 1
입력
```
10
1 2 3 4 1 4 3 2 1 6
```
예상 출력
```
6
```