D. Petya, Petya, Petr, and Palindromes
binary search; brute force; data structures; two pointers
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\).