题目描述

给出一个数组 a[1...n] ，如果数组同时满足如下两个条件，则称数组是"优美数组"：

1. 对于所有的 1 <= i <= n-2 ，都满足 a[i] = a[i+2]。

2. 数组 a 含有两种不同的数。

为了使得 a 数组是"优美数组"，你可以使用魔法，每使用一次魔法，你可以使得 a 数组的某个位置的数变成你想要的任意一个数。

求最少需要多少次魔法，才能完成任务。

输入格式

第一行，一个整数 n ( 1 <= n <= ${10}^5$ ，且 n 是偶数 )。

第二行，n 个整数，第 i 个整数是 a[i] ( 1 <= a[i] <= ${10}^5$ )。

输出格式

一个整数。

样例

4
3 1 3 2

1

6
105 119 105 119 105 119

0

4
1 1 1 1

2