Bored with the standard two-dimensional artwork (and also frustrated that others copy her work), the great artist Picouso decided to move towards a more minimalist, one-dimensional style. Her final painting can be described by a one-dimensional array of colors of length
N (
\(1<=N<=300\)), where each color is specified an integer in the range
\(1…N\).
Much to Picouso's dismay, her rival Mune seems to have figured out how to replicate even these one-dimensional paintings! Mune paints one interval with one color, waits for it to dry, then paints another interval, and so on. Mune can use each of the
N colors as many times as she wants (possibly none).
Calculate the minimum number of brush strokes with one color that Muna needs to copy a Picouso painting.
Input
The first line contains the number
N. The next line contains
N integers in the range
\(1…N\) indicating the color of each cell in Picouso's painting.
Imprint
Print the minimum number of brush strokes to copy the painting.
Examples
| # |
Input |
Output |
| 1 |
10
1 2 3 4 1 4 3 2 1 6
| 6 |
Explanation
In this example, Mounet can copy the picture like this: (unfilled cells are indicated by color 0).
Initially, the entire array is unfilled:
0 0 0 0 0 0 0 0 0 0
Mune paints the first 9 cells with color 1:
1 1 1 1 1 1 1 1 1 0
Mune paints the interval with color 2:
1 2 2 2 2 2 2 2 1 0
Mune paints the interval with color 3:
1 2 3 3 3 3 3 2 1 0
Mune paints the interval with color 4:
1 2 3 4 4 4 3 2 1 0
Mune paints one cell with color 1:
1 2 3 4 1 4 3 2 1 0
Mune paints the last cell with color 6:
1 2 3 4 1 4 3 2 1 6
Note that on the first stroke of the brush, it was possible to paint over the tenth cell with color 1. It wouldn't change the final state.