题目：数字移动（最小单次操作体力上限）

题目描述

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

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

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

重要理解：

• 如果某个数字的值 > ( x )，那么它不能被移动（因为移动它的体力消耗会超过 ( x )）
• 只能移动值 ≤ ( x ) 的数字
• 所有 > ( x ) 的数字必须保持不动，它们原本的位置不能改变

输入格式

第一行一个正整数 ( N )，代表序列长度，保证 ( N ) 为偶数。

第二行包含 ( N ) 个正整数 $\red{A=A_1,A_2,....,A_N}$，代表序列 ( A )。且对于任意 $\red{ 1 <= i <= N }$，存在唯一一个 $\red{ j}$ 满足 $\red{1 <= j <= N, i != j, A_i = A_j }$。

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

输出格式

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

输入输出样例

样例输入 #1

6
1 2 1 3 2 3

样例输出 #1

2

样例解释

• 当 ( x=1 ) 时，只能移动数字 1，不能移动数字 2 和 3，无法完成任务
• 当 ( x=2 ) 时，可以移动数字 1 和 2，方案如下：
  • 将第 2 个位置的数字 2 移动到第 3 个位置 1 的后面
  • 序列变为 [1, 1, 2, 3, 2, 3]
  • 再将第 5 个位置的数字 2 移动到第 4 个位置 3 的后面
  • 序列变为 [1, 1, 2, 2, 3, 3]
  • 每次操作体力消耗分别为 2 和 2，均不超过 2

说明/提示

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

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