Score : $500$ points

问题描述

对于一个序列 $X$，令 $f(X) =$ （将 $X$ 改造为回文串所需的最少元素修改次数）。

给定长度为 $N$ 的序列 $A$，求 $A$ 中所有 连续 子数组的 $f(X)$ 值之和。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For a sequence $X$, let $f(X) =$ (the minimum number of elements one must modify to make $X$ a palindrome).

Given a sequence $A$ of length $N$, find the sum of $f(X)$ over all contiguous subarrays of $A$.

Here, a sequence $X$ of length $m$ is said to be a palindrome if and only if the $i$-th and the $(m+1-i)$-th elements of $X$ are equal for all $1 \le i \le m$.

Constraints

• All values in the input are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$

Input

The input is given from Standard Input in the following format:

$N$

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

Output

Print the answer as an integer.

Sample Input 1

5
5 2 1 2 2

Sample Output 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$

Therefore, the sought answer is $9$.

update @ 2024/3/10 12:07:15