310275: CF1808D. Petya, Petya, Petr, and Palindromes

D. Petya, Petya, Petr, and Palindromestime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

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

ExamplesInput

8 5
1 2 8 2 5 2 8 6

Output

4

Input

9 9
1 2 3 4 5 4 3 2 1

Output

0

Note

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$.

题目大意：
Petya和他的机器人朋友Petya++有一个共同的朋友——半机械人Petr#。Petr#有时会来找他们喝茶，并告诉他们有趣的问题。今天，Petr#告诉他们以下问题。

回文是一种从左到右和从右到左读取相同的序列。例如，\[38, 12, 8, 12, 38\]，\[1\]，和\[3, 8, 8, 3\]都是回文。

我们称序列\[a_1, a_2, \ldots, a_n\]的“回文性”为使该序列成为回文所需替换的最小元素数量。例如，序列\[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}, \ldots, a_{i+k-1}\]的回文性值的总和。

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

输入输出数据格式：
输入：
第一行包含两个整数\[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\]）——序列本身。

输出：
输出一个整数——所有长度为\[k\]的子数组的回文性之和。

示例：
输入：
```
8 5
1 2 8 2 5 2 8 6
```
输出：
```
4
```

输入：
```
9 9
1 2 3 4 5 4 3 2 1
```
输出：
```
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。题目大意： Petya和他的机器人朋友Petya++有一个共同的朋友——半机械人Petr#。Petr#有时会来找他们喝茶，并告诉他们有趣的问题。今天，Petr#告诉他们以下问题。 回文是一种从左到右和从右到左读取相同的序列。例如，\[38, 12, 8, 12, 38\]，\[1\]，和\[3, 8, 8, 3\]都是回文。 我们称序列\[a_1, a_2, \ldots, a_n\]的“回文性”为使该序列成为回文所需替换的最小元素数量。例如，序列\[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}, \ldots, a_{i+k-1}\]的回文性值的总和。 学生们很快就解决了这个问题。你能做到吗？ 输入输出数据格式： 输入： 第一行包含两个整数\[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\]）——序列本身。 输出： 输出一个整数——所有长度为\[k\]的子数组的回文性之和。 示例： 输入： ``` 8 5 1 2 8 2 5 2 8 6 ``` 输出： ``` 4 ``` 输入： ``` 9 9 1 2 3 4 5 4 3 2 1 ``` 输出： ``` 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。