题目描述

很多人都以为哥萨克胡子最喜欢的数字是七。然而，他们错了。实际上他最喜欢的数字是二。正因如此，他只喜欢那些恰好包含两个不同数字的数组。

尽管如此，普通的那种只包含两个不同数字的数组在他看来还是太过混乱，而哥萨克讨厌混乱。所以，他只喜欢那些任意两个相邻元素都互不相同的数组。

正式地说，要使一个数组令胡子满意，需要满足以下条件：

• 对所有 $i$ ($1 \leq i \leq n - 2$) 满足 $a_i = a_{i+2}$；
• 对所有 $i$ ($1 \leq i \leq 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_1, a_2, \dots, a_n$ 的数组 $a$。你需要修改最少数量的数字，使得这个数组能让哥萨克胡子满意。找出这个最少修改数量。

例如，在数组 $[1, 1, 1, 1, 1]$ 中，需要将第二个和第四个元素改为任意其他数字。因此在这个例子中，答案是 $2$。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$) —— 数组中的数字个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) —— 数组中的数字。

输出格式

输出需要修改的最少数字数量，以使数组符合哥萨克的喜好。

6
1 4 5 4 1 5

2

8
1 2 1 2 1 2 1 2

0

5
1 1 1 1 1

2

提示

评分细则

在限制条件 $n \leq 100$ 且 $a_i \leq 100$ 下能正确运行的解决方案将获得 $40$ 分。

翻译由 DeepSeek V3 完成