配点 : $500$ 点

問題文

数列 $X$ に対し、 $f(X) =$ ( $X$ を回文にするために変更する必要のある要素の個数の最小値 ) とします。

与えられた長さ $N$ の数列 $A$ の全ての 連続 部分列 $X$ に対する $f(X)$ の総和を求めてください。

但し、長さ $m$ の数列 $X$ が回文であるとは、全ての $1 \le i \le m$ を満たす整数 $i$ について、 $X$ の $i$ 項目と $m+1-i$ 項目が等しいことを指します。

制約

• 入力は全て整数
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

出力

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

5
5 2 1 2 2

9

• $f(5) = 0$
• $f(2) = 0$
• $f(1) = 0$
• $f(2) = 0$
• $f(2) = 0$
• $f(5,2) = 1$
• $f(2,1) = 1$
• $f(1,2) = 1$
• $f(2,2) = 0$
• $f(5,2,1) = 1$
• $f(2,1,2) = 0$
• $f(1,2,2) = 1$
• $f(5,2,1,2) = 2$
• $f(2,1,2,2) = 1$
• $f(5,2,1,2,2) = 1$

以上より、求める答えは $9$ です。