問題文

数列 $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$

出力

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

入力例 1

5
5 2 1 2 2

出力例 1

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$ です。