优美数组

题目描述

Y 同学非常喜欢数字 $2$。因此，他特别偏爱那些恰好只包含两种不同数字的数组。

然而，普通的仅包含两种数字的数组在 Y 同学看来仍然不够整洁，因为他极度讨厌混乱。他希望数组具有严格的交替规律，即任意两个相邻的元素都必须互不相同。

形式化地，一个长度为 $n$ 的数组 $A = \{a_1, a_2, \ldots, a_n\}$ 能让 Y 同学感到满意，当且仅当它同时满足以下两个条件：

1. 对于所有 $1 \le i \le n - 2$，都满足 $a_i = a_{i+2}$。
2. 对于所有 $1 \le i \le n - 1$，都满足 $a_i \neq a_{i+1}$。

例如，数组 $\{1, 4, 1, 4, 1\}$ 是令人满意的，因为它只包含 $1$ 和 $4$ 两种数字，且相邻元素互不相同。 但是数组 $\{1, 4, 5\}$ 不令人满意（因为它包含了三种不同的数字），数组 $\{1, 1, 1, 1, 1\}$ 也不令人满意（相邻元素相同，且只包含一种数字），数组 $\{7, 7, 6, 6\}$ 同样不令人满意（因为存在相同的相邻元素）。

现在，给定一个包含 $n$ 个整数的数组 $A$。Y 同学每次操作可以修改数组中的任意一个元素为其它的任意正整数。请你计算，最少需要修改多少个数字，才能使该数组变得让 Y 同学满意？

例如，在数组 $\{1, 1, 1, 1, 1\}$ 中，可以将第二个和第四个元素修改为任意其它相同的数字（比如修改为 $2$，得到 $\{1, 2, 1, 2, 1\}$），因此最少需要修改 $2$ 个数字。

输入格式

第一行包含一个整数 $n$，表示数组中数字的个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始的数组 $A$。

输出格式

输出一行一个整数，表示使数组符合 Y 同学喜好所需的最少修改次数。

样例

样例输入 #1

6
1 4 5 4 1 5

样例输出 #1

2

样例输入 #2

8
1 2 1 2 1 2 1 2

样例输出 #2

0

样例输入 #3

5
1 1 1 1 1

样例输出 #3

2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$。