У мальчика Пети и его друга, робота Petya++, есть общий друг — киборг Petr#. Иногда Petr# заходит к ребятам на чай и рассказывает интересные задачи.
Сегодня Petr# рассказал следующую задачу.
Палиндромом называется последовательность, которая одинаково читается как слева направо, так и справа налево. Например, \([38, 12, 8, 12, 38]\), \([1]\) и \([3, 8, 8, 3]\) — палиндромы.
Назовем палиндромностью последовательности \(a_1, a_2, \dots, a_n\) минимальное количество чисел, которое необходимо заменить, чтобы эта последовательность стала палиндромом. Например, палиндромность последовательности \([38, 12, 8, 38, 38]\) равна \(1\), поскольку достаточно лишь заменить число \(38\) на четвертой позиции на число \(12\). А палиндромность последовательности \([3, 3, 5, 5, 5]\) равна двум, так как можно заменить тройки на первых двух позициях на пятерки, и полученная последовательность \([5, 5, 5, 5, 5]\) станет палиндромом.
Дана последовательность \(a\) длины \(n\). Также дано некоторое нечетное число \(k\). Необходимо найти суммарную палиндромность всех подмассивов длины \(k\), то есть сумму по значениям палиндромности последовательностей \(a_i, a_{i+1}, \dots, a_{i+k-1}\) для всех \(i\) от \(1\) до \(n-k+1\).
Ребята быстро справились с задачей Petr#. А Вы сможете?
Примечание
В первом примере палиндромность подмассива \([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\).