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? 

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 a single integer — the total palindromicity of all subarrays of length $ 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 $ .