题目描述

小A 有⼀个包含 $N$ 个正整数的序列$A=${$A_1,A_2,...,A_N$} ，序列$A$ 恰好包含 $\frac{N}{2}$ 对不同的正整数。形式化地，对于任意$1\leq i \leq N$ ，存在唯⼀⼀个$j$满足 。 小 A 希望每对相同的数字在序列中相邻，为了实现这⼀目的，小 A 每次操作会选择任意$i$ ($1\leq i \leq N$)，将当前序列的第 $i$ 个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列 $A=${$1,2,1,3,2,3$} ，小 A 可以选择 $i=2$，将 $A_2=2$ 移动到 $A_3=1$ 的后⾯，此时序列变为 {$1,1,2,3,2,3$} ，耗费$2$ 点体力。小 A 也可以选择 $i=3$，将 $A_3=1$ 移动到 $A_2=2$的前面，此时序列变为 {$1,1,2,3,2,3$} ，花费 $1$ 点体力。

小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出⼀个最小的$x$ ，使得他能够在每次花费的体力均不超过 $x$ 的情况下令每对相同的数字在序列中相邻。

输入格式

第⼀行⼀个正整数 $N$，代表序列长度，保证 $N$ 为偶数。

第二行包含 $N$ 个正整数$A_1,A_2,...,A_N$ ，代表序列$A$。且对于任意 $1\leq i \leq N$，存在唯⼀⼀个 $j$ 满足$1\leq j \leq N ,i\neq j, A_i=A_j$。

数据保证小 A 至少需要执行⼀次操作。

输出格式

输出⼀行，代表满足要求的 $x$ 的最小值。

样例

6
1 2 1 3 2 3

2

数据范围

对于40%的测试点，保证 $1\leq N,A_i \leq 100$。

对于所有测试点，保证$1\leq N,A_i \leq 10^5$ 。