| Codeforces Round 861 (Div. 2) |
|---|
| Закончено |
У мальчика Пети и его друга, робота 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#. А Вы сможете?
В первой строке входных данных находится два целых числа $$$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$$$.
