Range Editing

Time limit4sMemory limit2048 MB

Summary

Given a row of n cells with target values (0 means empty), find the minimum number of range assign and range clear operations to reach them.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

Problem

A spreadsheet has a row of 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 cells in the range get the same value after this operation.
Select a consecutive range of cells and delete their values. All cells in the range become empty after this operation.

Given the final cell values you want, calculate the minimum number of editing operations required to obtain them.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 800$ ), the number of cells. The cells are numbered 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$ -th line is $0$ if cell $i$ should be empty after all operations. Otherwise, it is the final value of cell $i$ .

Output

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

Examples1

Example 1
Input
```
10
0
1
2
3
4
2
1
0
0
1
```
Expected output
```
5
```