Petya 和他的朋友机器人 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$$$,因为用数字 $$$12$$$ 替换第四个位置的数字 $$$38$$$ 就足够了。序列 $$$[3, 3, 5, 5, 5]$$$ 的回文性是 2,因为您可以用 5 替换前两个 3,并且生成的序列 $$$[5, 5, 5, 5, 5]$$$ 是回文。
给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和一个奇数 $$$k$$$,您需要找到长度为 $$$k$$$ 的所有子数组的回文性之和,i。 即,从 $$$1$$$ 到 $$$n-k+1$$$ 的所有 $$$i$$$ 的序列 $$$a_i, a_{i+1}, \dots, 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$$$ 的子数组的总回文性。
示例
输入 #1
8 5 1 2 8 2 5 2 8 6
输出 #1
4
输入 #2
9 9 1 2 3 4 5 4 3 2 1
输出 #2
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$$$。