Problem H
Range Editing
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.
Input
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
Output a single integer, which the minimum number of editing operations required.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 0 1 2 3 4 2 1 0 0 1 |
5 |
