#G1149. [GESP202512 五级] 数字移动

[GESP202512 五级] 数字移动

[GESP202512 五级] 数字移动

题目描述

小 A 有一个包含 NN 个正整数的序列 A={A1,A2,…,AN}A = \{A_1, A_2, \dots, A_N\},序列 AA 恰好包含 N2\frac{N}{2} 对不同的正整数。形式化地,对于任意 1≤i≤N1 \leq i \leq N,存在唯一一个 jj 满足 1≤j≤N,i≠j,Ai=Aj1 \leq j \leq N, i \neq j, A_i = A_j。

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

例如,假设序列 A={1,2,1,3,2,3}A = \{1, 2, 1, 3, 2, 3\},小 A 可以选择 i=2i = 2,将 A2=2A_2 = 2 移动到 A3=1A_3 = 1 的后面,此时序列变为 {1,1,2,3,2,3}\{1, 1, 2, 3, 2, 3\},耗费 2 点体力。小 A 也可以选择 i=3i = 3,将 A3=1A_3 = 1 移动到 A2=2A_2 = 2 的前面,此时序列变为 {1,1,2,3,2,3}\{1, 1, 2, 3, 2, 3\},花费 1 点体力。

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

输入格式

第一行一个正整数 NN,代表序列长度,保证 NN 为偶数。

第二行包含 NN 个正整数 A1,A2,…,ANA_1, A_2, \dots, A_N,代表序列 AA。且对于任意 1≤i≤N1 \leq i \leq N,存在唯一一个 jj 满足 1≤j≤N,i≠j,Ai=Aj1 \leq j \leq N, i \neq j, A_i = A_j。

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

输出格式

输出一行,代表满足要求的 xx 的最小值。

样例 #1

样例输入 #1

6
1 2 1 3 2 3

样例输出 #1

2

数据范围

测试点占比 约束
40% 1≤N,Ai≤1001 \leq N, A_i \leq 100
100% 1≤N,Ai≤1051 \leq N, A_i \leq 10^5