Painting stones

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 1\,000;

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