题目描述

对于一个序列$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$

输出

打印一个整数作为答案。

示例输入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$。