数字移动

题目描述

小 A 有一个包含 n 个正整数的序列 a，序列 a 恰好包含 n/2 对不同（值两两相同）的正整数。形式化地，对于任意 i，存在唯一一个 j 满足 a[i] = a[j]。

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

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

输入格式

第一行一个正整数 n，代表序列长度，保证 n 为偶数。 第二行包含 n 个正整数 a[1], a[2], ..., a[n]，代表序列 a。数据保证对于任意 i，存在唯一一个 j 满足 a[i] = a[j]。

输出格式

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

样例

输入样例

6 1 2 1 3 2 3

输出样例

2

样例解释

序列 1 2 1 3 2 3 中，数值大于 2 的元素为 3, 3，已相邻；数值不超过 2 的元素可自由移动。最小 x = 2。

数据范围

对于所有测试点，保证 2 <= n <= 10^5 且 n 为偶数，1 <= a[i] <= 10^6，且每个值在序列中恰好出现两次。