Modern Art 3

Time limit1sMemory limit512 MB

Summary

Given a 1D painting of N colors, find the minimum number of brush strokes (each painting one interval in one color, later strokes over earlier ones) needed to reproduce it.

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

Problem

Having grown bored with ordinary 2-dimensional artwork, and annoyed that other cows keep copying her work, the great bovine artist Picowso has switched to a simpler 1-dimensional style. Her latest painting is a 1-dimensional array of colors of length $N$ ( $1 \leq N \leq 300$ ), where each color is an integer in the range $1\ldots N$ .

To Picowso's dismay, her rival Moonet has figured out how to copy even these 1-dimensional paintings. Moonet paints one interval with one color, waits for it to dry, then paints another interval, and so on. Moonet may use each of the $N$ colors as many times as she likes, including not at all.

Compute the number of brush strokes Moonet needs to copy Picowso's latest 1-dimensional painting.

Input

The first line contains $N$ .

The next line contains $N$ integers in the range $1 \ldots N$ giving the color of each cell in Picowso's latest 1-dimensional painting.

Output

Print the minimum number of brush strokes needed to copy the painting.

Examples1

Example 1
Input
```
10
1 2 3 4 1 4 3 2 1 6
```
Expected output
```
6
```