题目描述

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

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

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

输入格式

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

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

输出格式

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

题目大意

对于一个序列 $X$，我们设函数 $f(X)$ 表示将 $X$ 修改为回文串需要修改的数的数量。

现在，给定一个长度为 $N$ 的序列 $A$，问 $A$ 的所有连续的子序列（也就是子串）的 $f(X)$ 的值的和

5
5 2 1 2 2

9

提示

制約

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

Sample Explanation 1

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