Minimal Brush Strokes for 1D Painting

In this problem, you are given a one-dimensional painting represented by an array of length \(N\) (\(1 \leq N \leq 300\)), where each element represents a color (an integer between 1 and \(N\)).

The rival artist paints by repeatedly painting an interval with a single color. He can paint an interval, let the paint dry and then paint another interval. He is allowed to use each of the \(N\) colors arbitrarily many times (or not at all). The painting operations can overlap, and later operations override earlier ones.

Your task is to determine the minimum number of painting operations (strokes) required to exactly reproduce the given painting.

Note: It is always optimal to paint a contiguous interval in one operation, and by careful overlapping, some operations may cover parts of previous strokes. A dynamic programming solution with a recurrence relation in \(O(N^3)\) is sufficient given \(N \leq 300\).

inputFormat

The input consists of two lines:

1. The first line contains an integer \(N\), the number of elements in the painting.
2. The second line contains \(N\) space-separated integers, where the \(i\)-th integer denotes the color at position \(i\) in the painting.

It is guaranteed that \(1 \leq N \leq 300\) and each color is an integer between 1 and \(N\) (inclusive).

outputFormat

Output a single integer, the minimal number of painting operations required to replicate the painting.

sample

3
1 2 1

2