CF1808D.Petya, Petya, Petr, and Palindromes

Petya and his friend, the robot Petya++, have a common friend — the cyborg Petr#. Sometimes Petr# comes to the friends for a cup of tea and tells them interesting problems.

Today, Petr# told them the following problem.

A palindrome is a sequence that reads the same from left to right as from right to left. For example, $[38, 12, 8, 12, 38]$, $[1]$, and $[3, 8, 8, 3]$ are palindromes.

Let's call the palindromicity of a sequence $a_1, a_2, \dots, a_n$ the minimum count of elements that need to be replaced to make this sequence a palindrome. For example, the palindromicity of the sequence $[38, 12, 8, 38, 38]$ is $1$ since it is sufficient to replace the number $38$ at the fourth position with the number $12$. And the palindromicity of the sequence $[3, 3, 5, 5, 5]$ is two since you can replace the first two threes with fives, and the resulting sequence $[5, 5, 5, 5, 5]$ is a palindrome.

Given a sequence $a$ of length $n$, and an odd integer $k$, you need to find the sum of palindromicity of all subarrays of length $k$, i. e., the sum of the palindromicity values for the sequences $a_i, a_{i+1}, \dots, a_{i+k-1}$ for all $i$ from $1$ to $n-k+1$.

The students quickly solved the problem. Can you do it too?

佩佳和他的朋友——机器人佩佳++，有一个共同的朋友——赛博格彼得#。有时彼得#会来拜访这两位朋友，一起喝杯茶，并给他们讲一些有趣的问题。

今天，彼得#给他们讲了下面这个问题。

回文序列是指从左到右读与从右到左读完全相同的序列。例如，$[38, 12, 8, 12, 38]$、$[1]$ 和 $[3, 8, 8, 3]$ 都是回文序列。

我们定义一个序列 $a_1, a_2, \dots, a_n$ 的回文度（palindromicity）为：使其变为回文序列所需修改的最少元素个数。例如，序列 $[38, 12, 8, 38, 38]$ 的回文度为 $1$，因为只需将第四个位置上的 $38$ 替换为 $12$ 即可；而序列 $[3, 3, 5, 5, 5]$ 的回文度为 $2$，因为可以将前两个 $3$ 替换为 $5$，从而得到回文序列 $[5, 5, 5, 5, 5]$。

给定一个长度为 $n$ 的序列 $a$ 和一个奇数 $k$，你需要计算所有长度为 $k$ 的连续子数组（即对所有 $i$ 从 $1$ 到 $n-k+1$，子数组 $a_i, a_{i+1}, \dots, a_{i+k-1}$）的回文度之和。

学生们很快解决了这个问题。你也能做到吗？

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le n$, $k$ is odd) — the length of the sequence and the length of subarrays for which it is necessary to determine whether they are palindromes.

The second line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the sequence itself.

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le n$，且 $k$ 为奇数）——分别表示序列的长度，以及需要判断是否为回文的子数组的长度。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）——即该序列本身。

Output a single integer — the total palindromicity of all subarrays of length $k$.

输出一个整数——所有长度为 $k$ 的子数组的总回文度。

In the first example, the palindromicity of the subarray $[1, 2, 8, 2, 5]$ is $1$, the palindromicity of the string $[2, 8, 2, 5, 2]$ is also $1$, the palindromicity of the string $[8, 2, 5, 2, 8]$ is $0$, and the palindromicity of the string $[2, 5, 2, 8, 6]$ is $2$. The total palindromicity is $1+1+0+2 = 4$.

In the second example, the only substring of length $9$ coincides with the entire string, and its palindromicity is $0$, so the answer is also $0$.

在第一个例子中，子数组 $[1, 2, 8, 2, 5]$ 的回文度为 $1$，字符串 $[2, 8, 2, 5, 2]$ 的回文度也为 $1$，字符串 $[8, 2, 5, 2, 8]$ 的回文度为 $0$，字符串 $[2, 5, 2, 8, 6]$ 的回文度为 $2$。总回文度为 $1+1+0+2 = 4$。

在第二个例子中，唯一长度为 $9$ 的子串即为整个字符串本身，其回文度为 $0$，因此答案也为 $0$。