KAIBUNsyo

题目描述

给定长度为 $N$ 的正整数序列：$A=(A_1,A_2, \dots A_N)$。 你可以对下面的操作执行零次或多次。至少需要做多少次操作才能使 $A$ 变为回文？

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

这里，当且仅当对每个 $i$（$1 \le i \le N$）都满足 $A_i=A_{N+1-i}$ 时，我们称 $A$ 为回文。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出一个整数，表示答案。

8
1 5 3 2 5 2 3 1

2

7
1 2 3 4 1 2 3

1

1
200000

0

提示

输入中的所有数值均为整数。 $1 \le N \le 2 \times 10^5$ $1 \le A_i \le 2 \times 10^5$最开始，序列为 $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$ 变为回文，并且这是所需的最小次数。
$A$ 也可能一开始就是回文。

标签: AtCoder|abc206D

来源

AtCoder|abc206D