题目描述

小蓝认为，一个序列是“好的”，当且仅当它满足以下条件：

1. 序列中恰好只出现两种不同的整数；
2. 任意一对相邻元素都不相同；
3. 对所有合法的下标 $i$（$1 \le i \le n - 2$），都有 $a_i = a_{i+2}$。

等价地说，一个好的序列一定形如

或

其中 $x \ne y$，且整个序列中只出现这两个数。

现在，小蓝有一个长度为 $n$ 的序列，他可以进行任意次修改操作。每次操作可以将序列中的一个元素改成任意正整数。

小蓝想知道：至少需要修改多少个元素，才能将当前序列变成一个好的序列？

输入格式

输入共两行。

第一行包含一个正整数 $n$，表示序列长度。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示小蓝当前的序列。

输出格式

输出一行，包含一个非负整数 $c$，表示至少需要修改 $c$ 个元素，才能使该序列变成一个好的序列。

5
1 1 1 1 2

2

解释 #1

一种最优方案是将第 $1$ 个和第 $3$ 个数改为 $2$，此时序列变为：

这是一个好的序列。可以验证，不存在只修改 $1$ 个元素就能满足条件的方案，因此答案为 $2$。

数据范围

• 对于 $30\%$ 的评测用例，$n \le 8$；
• 另有 $20\%$ 的评测用例满足：对所有 $1 \le i, j \le n$，都有 $a_i = a_j$；
• 对于所有评测用例，$2 \le n \le 10^6$，且 $1 \le a_i \le 10^6$。