题目描述

$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$ $\dots$ $A_N$

输出格式

答えを整数として出力せよ。

题目大意

给你一个长度为 $N$ 的正数序列：$A= \{A_1,A_2, \cdots , A_N \}$。你可以做下边的操作零或者更多次，至少多少次操作能让序列 $A$ 变成回文序列？

• 选择一对正数 $(x,y)$ ，然后将序列中的每一个 $x$ 都换为 $y$ 。

注：我们说 $A$ 是一个回文序列，当且仅当对于序列中每个元素，都有 $A_i=A_{N+1-i}(1 \leq i \leq 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$

Sample Explanation 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$ を $2$ 回の操作で回文にすることができ、これが最小です。

Sample Explanation 3

$A$ がはじめから回文である可能性もあります。