数字移动

题目描述

⼩ A 有⼀个包含 个正整数的序列 ，序列 恰好包含 对不同的正整数。形式化地，对于 任意 ，存在唯⼀⼀个 满⾜ 。 ⼩ A 希望每对相同的数字在序列中相邻，为了实现这⼀⽬的，⼩ A 每次操作会选择任意 ( )，将当前序列 的第 个数字移动到任意位置，并花费对应数字的体⼒。 例如，假设序列 ，⼩ A 可以选择 ，将 移动到 的后⾯，此时序列变为 ，耗费 点体⼒。⼩ A 也可以选择 ，将 移动到 的前⾯，此时序列变为 ，花费 点体⼒。 ⼩ A 可以执⾏任意次操作，但他希望⾃⼰每次花费的体⼒尽可能⼩。⼩ A 希望你能帮他计算出⼀个最⼩的 ，使得 他能够在每次花费的体⼒均不超过 的情况下令每对相同的数字在序列中相邻。

输入格式

第⼀⾏⼀个正整数 ，代表序列长度，保证 为偶数。 第⼆⾏包含 个正整数 ，代表序列 。且对于任意 ，存在唯⼀⼀个 满⾜ 。 数据保证⼩ A ⾄少需要执⾏⼀次操作。

输出格式

输出⼀⾏，代表满⾜要求的 的最⼩值。

样例输入 #1

6
1 2 1 3 2 3

样例输出 #1

2

数据范围

对于40%的测试点，保证 。 对于所有测试点，保证 。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。