Range Editing

시간 제한4초메모리 제한2048 MB

요약

모두 비어 있는 상태에서 시작해 범위 채우기와 범위 지우기만으로 주어진 셀 값 배열을 만드는 최소 연산 횟수를 구한다.

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

문제

You are editing a list of spreadsheet cells. Initially all cells are empty. You can perform two types of operations:

Select a consecutive range of cells and change their values to a positive integer of your choice. All these cells get the same value after this operation.
Select a consecutive range of cells and delete their values. All these cells become empty after this operation.

Given the final cell values that you would like to have in the spreadsheet, calculate the minimum number of editing operations required to obtain those values.

입력

The first line of input contains a single integer $n$ ( $1 \leq n \leq 800$ ), which is the number of cells you are editing. The cells are number from $1$ to $n$ .

Each of the next $n$ lines contains a single integer between $0$ and $10^9$ inclusive. The integer on the $i^{\text{th}}$ line is $0$ if cell $i$ should be empty after all operations. Otherwise, it is a positive integer that is the final value of cell $i$ .

출력

Output a single integer, which the minimum number of editing operations required.

예제1

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