AT_abc206_d [ABC206D] KAIBUNsyo

题目描述

给定一个由 $N$ 项组成的正整数序列 $A=(A_1,A_2,\ \dots\ A_N)$。
你可以进行如下操作任意多次（包括 $0$ 次）：

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

请问，最少需要进行多少次操作，才能使 $A$ 变为回文序列？

在本题中，当且仅当对于所有整数 $i$（$1\le i\le N$），都有 $A_i=A_{N+1-i}$ 时，$A$ 被称为回文序列。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出一个整数，表示最少需要进行的操作次数。

输入输出样例 #1

输入 #1

8
1 5 3 2 5 2 3 1

输出 #1

2

输入输出样例 #2

输入 #2

7
1 2 3 4 1 2 3

输出 #2

1

输入输出样例 #3

输入 #3

1
200000

输出 #3

0

说明/提示

限制条件

• 输入均为整数。
• $1\le N\le 2\times 10^5$
• $1\le A_i\le 2\times 10^5$

样例解释 1

• 初始时，$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$ 变为回文序列，且这是最少的操作次数。

样例解释 3

$A$ 也有可能一开始就是回文序列。

由 ChatGPT 4.1 翻译