← 返回题目列表

AtCoder · abc290_e

H. 使其成为回文

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

对于序列 X,让 f(X) = (必须修改的元素的最小数量才能使 X 回文)。

给定一个序列 A 长度 N,求总和 f(X) 总的来说 连续 的子数组 A.

这里,一个序列 X 长度 m 被称为回文当且仅当 i-th 和 (m+1-i)第一个元素 X 对所有人来说都是平等的 1 \le i \le m.

约束

  • 输入中的所有值都是整数。
  • 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.