题目描述

给定一个由 $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$ 是一个回文序列。

约束条件

• 输入的所有值都是整数。
• $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$

输出

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

示例输入1

8
1 5 3 2 5 2 3 1

示例输出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$ 成为一个回文序列，这是所需的最小次数。

示例输入2

7
1 2 3 4 1 2 3

示例输出2

1

示例输入3

1
200000

示例输出3

0

开始时，$A$ 可能已经是一个回文序列。