Reference: Codeforces 1479B2 — Painting the Array II

You are given an array:

~a_1, a_2, \ldots, a_n~

Each element must be colored either white or black.

After coloring, form two subsequences:

• ~A_{white}~: all white elements in their original order;
• ~A_{black}~: all black elements in their original order.

For an array ~c~, define ~segments(c)~ as the length of the array after every group of equal adjacent values is compressed into one value.

For example:

[1, 1, 2, 2, 3, 3, 3, 2]

becomes:

[1, 2, 3, 2]

and therefore has ~4~ segments.

An empty array has ~0~ segments.

Color the original array so that:

~segments(A_{white}) + segments(A_{black})~

is as small as possible.

Input

• The first line contains one integer ~n~.
• The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

• Print one integer: the minimum possible total number of segments.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le a_i \le n~

Example 1

Input:

6
1 2 3 1 2 2

Output:

4