|Codeforces Round #538 (Div. 2)|
You are given a line of $$$n$$$ colored squares in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. The $$$i$$$-th square initially has the color $$$c_i$$$.
Let's say, that two squares $$$i$$$ and $$$j$$$ belong to the same connected component if $$$c_i = c_j$$$, and $$$c_i = c_k$$$ for all $$$k$$$ satisfying $$$i < k < j$$$. In other words, all squares on the segment from $$$i$$$ to $$$j$$$ should have the same color.
For example, the line $$$[3, 3, 3]$$$ has $$$1$$$ connected component, while the line $$$[5, 2, 4, 4]$$$ has $$$3$$$ connected components.
The game "flood fill" is played on the given line as follows:
Find the minimum number of turns needed for the entire line to be changed into a single color.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of squares.
The second line contains integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 5000$$$) — the initial colors of the squares.
Print a single integer — the minimum number of the turns needed.
4 5 2 2 1
8 4 5 2 2 1 3 5 5
In the first example, a possible way to achieve an optimal answer is to pick square with index $$$2$$$ as the starting square and then play as follows:
In the second example, a possible way to achieve an optimal answer is to pick square with index $$$5$$$ as the starting square and then perform recoloring into colors $$$2, 3, 5, 4$$$ in that order.
In the third example, the line already consists of one color only.