题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A=(A_1,A_2,\dots,A_N)$，且序列恰好由 $\dfrac{N}{2}$ 对不同的正整数构成。形式化地：对任意 $1\le i\le N$，存在且仅存在一个 $j\ne i$ 使得 $A_i=A_j$（即每个值恰好出现两次）。

小 A 希望将序列变换为“每对相同的数字在序列中相邻”的形式（例如 $\dots,x,x,\dots$）。允许的操作为：选择任意下标 $i$，把当前位置的数字 $A_i$ 移动到序列中的任意位置（插入到某个位置前或后），每次移动所消耗的体力等于被移动元素的数值（即移动值为 $v$ 的元素需付出 $v$ 点体力）。可以执行任意次操作。

小 A 希望限制每次操作的体力消耗都不超过某个阈值 $x$，并在该限制下能够完成目标（即最终使每对相同数字相邻）。请你计算使此目标可行的最小的 $x$ 值。

例如：$A=(1,2,1,3,2,3)$。把 $A_2=2$ 移到 $A_3$ 后面，序列变为 $(1,1,2,3,2,3)$，耗费 $2$；也可把 $A_3=1$ 移到 $A_2$ 前面，耗费 $1$。本题要求找到一个最小的 $x$，使得存在一系列每次移动耗费 $\le x$ 的操作，用以将序列整理为每对相同数字相邻的形式。

输入格式

• 第一行包含一个正整数 $N$，表示序列长度（保证 $N$ 为偶数）。
• 第二行包含 $N$ 个正整数 $A_1,A_2,\dots,A_N$，满足对任意 $1\le i\le N$，存在唯一的 $j\ne i$ 使得 $A_i=A_j$。

题目保证初始序列不是已经满足“每对相同数字相邻”，故至少需要一次操作。

输出格式

输出一行，包含一个整数：满足题目要求的最小 $x$。

样例输入 1

6
1 2 1 3 2 3

样例输出 1

2

说明

数据范围

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