$k$ -Even-Sum Sequence

Time limit1sMemory limit256 MB

Summary

Change the fewest elements so that every contiguous block of length k in the sequence has an even sum.

Level: Medium5 of 10
Topics: Greedy, Math, Prefix sum, Implementation
Solved: No attempts yet

Problem

You are given an integer sequence $a_1, a_2, \ldots, a_n$ . For every integer $i$ with $1 \le i \le n - k + 1$ , if the partial sum $a_i + a_{i+1} + \cdots + a_{i+k-1}$ is even, the sequence is called a $k$ -even-sum sequence.

In other words, the sum of every contiguous block of length $k$ must be even.

You may choose some elements of the sequence and change each of them to any integer you like. Find the minimum number of elements you must change to turn the sequence into a $k$ -even-sum sequence.

Input

The first line contains two integers $n$ and $k$ separated by a space. ( $1 \le k \le n \le 10^6$ )

The second line contains $n$ integers separated by spaces; the $i$ -th of them is $a_i$ . ( $0 \le a_i \le 10^9$ )

Output

Print the minimum number of elements that must be changed on a single line.

Examples4

Example 1
Input
```
8 3
1 2 3 4 5 6 7 8
```
Expected output
```
3
```
Example 2
Input
```
5 1
1 3 5 7 9
```
Expected output
```
5
```
Example 3
Input
```
5 1
2 4 6 8 10
```
Expected output
```
0
```
Example 4
Input
```
4 2
1 2 3 4
```
Expected output
```
2
```