#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Final Cut - Repovive Starter Round 7 | Repovive

21C. Final Cut

1500 pts1s256 MB

A movie consists of $n$ scenes shown in order. Scene $i$ features actor $a_i$ .

The final cut is called smooth if no two consecutive scenes feature the same actor.

The editor may delete at most one non-empty contiguous segment of scenes. The remaining scenes keep their relative order. The editor may also choose not to delete anything.

Find the minimum number of scenes that must be deleted to make the final cut smooth.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

Input

The input consists of two lines:

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output

Output one integer: the minimum number of scenes that must be deleted.

Samples

Input

7
1 2 1 3 2 3 1

Explanation

No two consecutive scenes feature the same actor, so no scene needs to be deleted.

Output

Input

7
1 2 2 3 4 4 2

Explanation

Delete scenes $3$ through $5$ . The remaining actor sequence is $1,2,4,2$ , which is smooth. Deleting fewer than three scenes cannot eliminate both repeated adjacent pairs with one contiguous deletion.

Output

Input

7
1 3 3 2 3 3 1

Explanation

Delete scenes $2$ through $5$ . The remaining actor sequence is $1,3,1$ , which is smooth. Any contiguous deletion of at most three scenes leaves two equal actors next to each other.

Output

A movie consists of $n$ scenes shown in order. Scene $i$ features actor $a_i$ .

The final cut is called smooth if no two consecutive scenes feature the same actor.

The editor may delete at most one non-empty contiguous segment of scenes. The remaining scenes keep their relative order. The editor may also choose not to delete anything.

Find the minimum number of scenes that must be deleted to make the final cut smooth.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

The input consists of two lines:

n

a_1 \quad a_2 \quad \cdots \quad a_n

Delete scenes $2$ through $5$ . The remaining actor sequence is $1,3,1$ , which is smooth. Any contiguous deletion of at most three scenes leaves two equal actors next to each other.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

21C. Final Cut

Constraints

Input

Output

Samples

21C. Final Cut

Constraints

Input

Output

Samples