405054: GYM101755 G Underpalindromity

Let us call underpalindromity of array b of length k the minimal number of times one need to increment some elements b_j by 1 so that the array b would become a palindrome, that is, b₁ = b_k, b₂ = b_k - 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 p_i. It's needed to calculate sum of all p_i (1 ≤ i ≤ n - k + 1).

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 a_i ( - 10⁸ ≤ a_i ≤ 10⁸) — the elements of the array.

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

3 2
3 1 2

3

5 3
2 3 3 1 4

4