Painting stones

You have in front of you $n$ stones, each of which is painted in a color, namely the $i$-th stone is painted in color $a_i$.

In one operation, you can choose any two adjacent stones and paint them in any same color.

You need all the stones to become the same color with the minimum number of operations.

Input

The first line contains one integer $n$ $(1\le n\le 2\cdot 10^5)$ — the number of stones.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$ — the colors of the stones.

Output

Output a single number — the minimum number of operations.

Examples

Note

In the first test, the stones are painted in colors $1,3,1,5,3,5$ respectively.

For the first operation, you can paint the stones at positions $4,5$ in color $1$, after which the stones will be $1,3,1,1,1,5$.

For the second operation, you can paint the stones at positions $1,2$ in color $1$. Now the stones are painted in $1,1,1,1,1,5$.

For the last operation, you can paint the last two stones in color $1$, after which all the stones will be of the same color ($1$).

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that the evaluation is still in progress.

1. ($32$ points): the number of different numbers among all $a_i$ is not more than $2$;

2. ($33$ points): $n\le 1000$;

3. ($35$ points): without additional constraints.