变成回文

题目描述

对于序列 $X$,定义 $f(X)$ 为使 $X$ 成为回文所需修改的元素个数的最小值。

给定长度为 $N$ 的序列 $A$,求 $f(X)$ 在所有 $A$ 的连续子数组上的和。

这里,长度为 $m$ 的序列 $X$ 被称为回文,当且仅当对所有 $1 \le i \le m$,$X$ 的第 $i$ 个元素与第 $(m+1-i)$ 个元素相等。

输入格式

输入按以下格式从标准输入给出:

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

数据范围

• 输入中的所有值均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$