小H觉得回文数字是非常美的,但是现实中遇到的数字串并非全部都是回文,因此小H要将连续若干个数变成回文,例如[2 4 6 4 3],最少改变数字数量1个,即2改成3或3改成2。但是仅仅这么算作为第四题太简单了,因此要加大难度。出题人除了给你n个数ai外,还给了你一个奇数m。由经验可知n个数可以划分出n-m+1个子串(每个子串个数为m),现在需要你计算出每个子串都转换为回文的变化总次数。当然为了加深小H对题目的理解,出题者对样例进行如下解释,
例如样例中可以生成4个子串,其中第一个子串[2 3 9 3 6]需要变化1次,第二个子串[3 9 3 6 3]需要变化次数为1,第三个子串[9 3 6 3 9]需要变化次数为0,[3 6 3 9 7]需要变化次数为2。所以答案就是1+1+0+2=4。
输入
第一行输入n和m。
第二行输入n个整数ai。
输出
输出所有子串变成回文的变化次数之和
样例输入
8 5
2 3 9 3 6 3 9 7
样例输出
4
数据规模:
70%数据 n<=300
100%数据 1<=m<=n<=10^6 (m保证为奇数) 1<=ai<=10^6
O(nm) 的会超时