当前没有测试数据。

E - 使它变成回文串

分数：500分

问题描述

对于一个序列$X$，定义$f(X)$为（使得$X$变成回文串所需修改的最小元素个数）。

给定一个长度为$N$的序列 $A$，计算所有连续子序列 $A$ 的 $f(X)$ 的和。

在这里，一个长度为$m$的序列$X$是回文串，当且仅当对于所有的$1 \le i \le m$，$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。