G. Underpalindromity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let us call underpalindromity of array b of length k the minimal number of times one need to increment some elements bj by 1 so that the array b would become a palindrome, that is, b1 = bk, b2 = bk - 1, and so on.

The array of length n, consisting of integers, is given. Consider all its subarrays of length k, and for each of these subarrays its underpalindromity pi. It's needed to calculate sum of all pi (1 ≤ i ≤ n - k + 1).

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200000) — the length of the array and the length of subarrays.

The second line contains n integers ai ( - 108 ≤ ai ≤ 108) — the elements of the array.

Output

Output a single integer — sum of underpalindromities of all subarrays of length k.

Examples
Input
3 2
3 1 2
Output
3
Input
5 3
2 3 3 1 4
Output
4