Sequence

Memory limit: 128 MB

We say that an integer sequence is -even if the sum of any consecutive terms of the sequnce is even.

For a given sequence we would like to find out how many of its terms need to be changed so that the sequence becomes -even.

Input

The first line of input contains two integers and (). The second line contains a sequence composed of integers . For each of the 's it holds that .

Output

The only line of output should hold one integer: the minimum number of terms of the sequence that need to be changed so that it becomes -even.

Example

For the input data:

8 3
1 2 3 4 5 6 7 8

the correct result is:

3

whereas for the input data:

8 3
2 4 2 4 2 4 2 4

the correct result is:

0

Task author: Jakub Radoszewski.