题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A=\{A_1,A_2,...,A_N\}$，序列 $A$ 恰好包含 $N/2$ 对不同的正整数。形式化地，对于任意 $1\le i\le N$，存在唯一一个 $j$ 满足 $1\le j\le N, i\ne j, A_i=A_j$。

小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 $i(1\le i\le N)$，将当前序列的第 $i$ 个数字移动到任意位置，并花费对应数字的体力。

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

输入格式

第一行一个正整数 $N$（偶数）。

第二行 $N$ 个正整数 $A_1,...,A_N$，每个值恰好出现两次。

数据保证至少需要一次操作。

输出格式

一行，满足要求的 $x$ 的最小值。

数据范围

• 对于 $40\%$ 的测试点，保证 $1\le N,A_i\le 100$。
• 对于所有测试点，保证 $1\le N,A_i\le 10^5$。

测试样例

6
1 2 1 3 2 3

2

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

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