31514번 - Range Editing 다국어

문제

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

1. 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.
2. 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.

제한

힌트