You are given a strip of checkered paper made of n colored squares numbered from 1 to n from left to right. The i-th square is initially colored c
i.
We say that squares i and j lie in the same 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 must have the same color.
For example, the strip [3,3,3] has 1 connected component, while [5,2,4,4] has 3.
Fill game is played on this strip as follows:
At the beginning of the game, you choose one random starting square (this does not count as a turn).
Then, on each move, you change the color of the connected component containing the starting square to any other color.
Find out the minimum number of moves needed to recolor the entire strip in one color.
Input:
The first line contains a single integer n (1 ≤ n ≤ 5000) — number of squares.
The second line contains the integers c
1,c
2,…,c
n (1 ≤ c
i <5000) — the initial colors of the squares.
Output:
Print a single integer — the minimum number of moves to make.
Examples:
| Input |
Output |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4 |
0 |
Explanation:
One of the optimal ways in the first example: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]