配点 : $400$ 点

問題文

$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$ が回文であると言います。

制約

• 入力は全て整数
• $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$

出力

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

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)$ となります。

以上の操作を行うと、$A$ を $2$ 回の操作で回文にすることができ、これが最小です。

7
1 2 3 4 1 2 3

1

1
200000

0

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