E - Make it Palindrome Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

数列 X に対し、 f(X) = ( X を回文にするために変更する必要のある要素の個数の最小値 ) とします。

与えられた長さ N の数列 A の全ての 連続 部分列 X に対する f(X) の総和を求めてください。

但し、長さ m の数列 X が回文であるとは、全ての 1 \le i \le m を満たす整数 i について、 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 です。

Score : 500 points

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.