D - 回文小

得分：400分

问题描述

给出一个长度为$N$的正整数序列$A=(A_1,A_2, \dots A_N)$。 你可以对其进行以下操作零次或多次。至少需要进行多少次操作使得$A$变成一个回文序列？

• 选择一对正整数$(x,y)$，将$A$中所有出现的$x$替换为$y$。

这里我们说$A$是一个回文序列，当且仅当对于任意的$i$ ($1 \le i \le N$)，满足$A_i=A_{N+1-i}$。

约束

• 输入数据中的所有值均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$

输入

输入数据从标准输入中读取，格式如下：

$N$

$A_1$ $A_2$ $\dots$ $A_N$

输出

输出结果为一个整数。

8
1 5 3 2 5 2 3 1

2

• 初始时，$A=(1,5,3,2,5,2,3,1)$。
• 将$A$中所有出现的$3$替换为$2$，得到$A=(1,5,2,2,5,2,2,1)$。
• 将$A$中所有出现的$2$替换为$5$，得到$A=(1,5,5,5,5,5,5,1)$。

通过这样的操作，我们可以在两步内将$A$变成一个回文序列，这是最少的次数。

7
1 2 3 4 1 2 3

1

1
200000

0

初始时$A$就已经是一个回文序列。