回文症

题目描述

给定由 $N$ 项组成的正整数序列 $A=(A_1,A_2, \dots A_N)$。

可以进行以下操作 0 次或多次，要使 $A$ 成为回文，最少需要进行多少次操作？

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

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

输入格式

输入按以下格式从标准输入给出：

N
A_1 A_2 … 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)$。

通过以上操作，可以用 2 次操作使 $A$ 成为回文，这是最少次数。

7
1 2 3 4 1 2 3

1

1
200000

0

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

数据范围

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