题目描述

Aki有n盆花，这n盆花由$\frac{n}{2}$对不同的花组成。相同的花有相同的美丽值$a_i$，不同的花美丽值不同。为了打理方便，Aki想让相同的花都是相邻的。

在这个问题里，Aki需要你帮忙调整花盆的位置。Aki每次可以将美丽值为$a_i$的花移动到任意位置，并且产生$a_i$的维护花费。

现在Aki想知道，如果给定某个花费限制X，在每次操作的花费都不超过X的情况下，就能把这n盆花调整至满足他需求的样子，那这个X最小是多少呢？

如 6 3 5 3 5 4 4 X=3时即可满足Aki的需求：把$a_3$移动到$a_1$后面即可，变成3 3 5 5 4 4。

输入格式

第一行一个正整数n，代表花的数量大小，$n<=10^5$，n保证是偶数 第二行n个正整数a[i]，每个$1<=a[i]<=10^9$

输入保证同一种花美丽值唯一，且同一种花刚好2盆。

输出格式

输出最小的花费限制X。

6
3 5 3 5 4 4

3

6
1 2 1 3 2 3

2