Deren has a line-shaped stick of n colored squares in a row, numbered from 1 to \(\mathbf{N}\) from left to right. The \(\mathbf{i}\)-th square initially has the color \(\mathbf{c_i}\).

Deren is color blind so he wants his stick's all squares to have the same color. Help him with painting his stick.

Deren can paint a connected component of the stick in one move. Let's say, that two squares i and j belong to the same connected component if \(\mathbf{c_i = c_j = c_k}\) for all k satisfying \(\mathbf{i < k < j}\). In other words, all squares on the segment from \(\mathbf{i}\) to \(\mathbf{j}\) should have the same color.

For example, the line [4,4,4] has 1 connected component, while the line [6,6,7,3] has 3 connected components.

Deren chooses a square at the start(this is not counted as a move). Then in every move he changes the color of the connected component containing the square he has picked to any other color. Help him find the minimum number of moves he needs to make in order to change his stick to a single color.

#### Input

The first line contains the integer \(\mathbf{N}\).

The second line contains integers \(\mathbf{c_1}\), \(\mathbf{c_2}\) ... \(\mathbf{c_n}\) - the initial colors of the squares.

##### Batch #1:

- \(1 \leq \mathbf{N} \leq 200\)
- \(1 \leq \mathbf{c_i} \leq 5000\)

##### Batch #2:

- \(1 \leq \mathbf{N} \leq 5000\)
- \(1 \leq \mathbf{c_i} \leq 5000\)

#### Output

Print a single integer — the minimum number of the moves needed.

#### Examples

Input:

```
6
1 0 1 1 0 1
```

Output:

`2`

Input:

```
11
0 1 2 3 0 2 4 2 2 3 4
```

Output:

`7`