Description

Tired of ordinary two-dimensional paintings (and also feeling upset because her work has been copied by others), the great cow artist Cowcasso decided to switch to a more minimalist one-dimensional style. Her latest painting can be described by a one-dimensional array of length $N$ ($1 \leq N \leq 300$), where each color is represented by an integer in $1 \ldots N$.

To Cowcasso’s frustration, her rival Moooo-net seems to have figured out how to copy these one-dimensional paintings anyway. Moooo-net paints an interval with one color, waits for the paint to dry, then paints another interval, and so on. Moooo-net may use each of the $N$ colors any number of times (or not at all).

Compute the minimum number of painting operations Moooo-net needs in order to copy Cowcasso’s latest one-dimensional painting.

Input Format

The first line contains $N$.

The next line contains $N$ integers in the range $1 \ldots N$, representing the color of each cell in Cowcasso’s latest one-dimensional painting.

Output Format

Output the minimum number of painting operations needed to copy this painting.

10
1 2 3 4 1 4 3 2 1 6

6

Hint

Explanation for Sample 1:

In this sample, Moooo-net can paint as follows. We use $0$ to represent an unpainted cell.

• Initially, the entire array is unpainted: 0 0 0 0 0 0 0 0 0 0
• Moooo-net paints the first nine cells with color $1$: 1 1 1 1 1 1 1 1 1 0
• Moooo-net paints an interval with color $2$: 1 2 2 2 2 2 2 2 1 0
• Moooo-net paints an interval with color $3$: 1 2 3 3 3 3 3 2 1 0
• Moooo-net paints an interval with color $4$: 1 2 3 4 4 4 3 2 1 0
• Moooo-net paints one cell with color $1$: 1 2 3 4 1 4 3 2 1 0
• Moooo-net paints the last cell with color $6$: 1 2 3 4 1 4 3 2 1 6

Note that in the first operation, Moooo-net could also paint the tenth cell with color $1$ at the same time as the first nine cells; this would not affect the final result.

Testdata Properties:

• For an additional $15\%$ of the testdata, only colors $1$ and $2$ appear in the painting.
• For an additional $30\%$ of the testdata, for each $1 \le i \le N$, the color of the $i$-th cell lies in the range $\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]$.
• For an additional $50\%$ of the testdata, there are no additional constraints.

Problem by: Brian Dean, Benjamin Qi

Translated by ChatGPT 5