Get Minimum Changes

Any element may be changed to a positive integer, and each changed position counts once. Every contiguous subarray of length k must have the same sum; find the minimum number of changes. Original elements may be non-positive; unchanged positions do not need to become positive. When k≥n, no change is needed.

输入格式

The first line contains n k; the second line contains the integer array. The original text had no numeric bounds; this site uses 1≤n,k≤200000, −10^9≤element≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 2
1 2 1 3

输出：

1

样例 2

输入：

2 1
-1 -1

输出：

0

样例 3

输入：

3 1
-1 -1 2

输出：

2

样例说明

The answers are 1, 0 and 2. In the last example 2 cannot be changed to −1; the only option is to change the two −1s to 2.