小 A 有一个包含N个正整数的序列A={A1,A2...,An} ，序列A 恰好包含 N/2对不同的正整数。形式化地，对于任意1<=i<=N ，存在唯一一个j 满足1<=j<=N,i!=j,Ai=Aj 。 小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意i (1<=i<=N )，将当前序列的第 i个数字移动到任意位置，并花费对应数字的体力。 例如，假设序列A={1,2,1,3,2,3} ，小 A 可以选择 i=2，将A2=2 移动到A3=1 的后面，此时序列变为{1,1,2,3,2,3} ，耗费 2点体力。小 A 也可以选择i=3 ，将A3=1 移动到A2=2 的前面，此时序列变为{1,1,2,3,2,3}，花费 1点体力。 小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的X ，使得他能够在每次花费的体力均不超过X 的情况下令每对相同的数字在序列中相邻。

第一行一个正整数N ，代表序列长度，保证N 为偶数。 第二行包含N个正整数A1,A2,...An ，代表序列 A。且对于任意 1<=i<=N，存在唯一一个 j满足1<=j<=N,i!=j,Ai=Aj。 数据保证小 A 至少需要执行一次操作。

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

数据范围 对于40%的测试点，保证1<=N,Ai<=100 。 对于所有测试点，保证1<=N,Ai<=10^5 。