Count Number of Nice Subarrays

Problem statement

A quality inspector marks a production record as special when its serial number is odd. The inspector needs to count all consecutive sections of the log containing exactly k special records, including sections with different boundaries but identical values. Your task Count nonempty contiguous subarrays containing exactly k odd integers. Important details Even values may appear anywhere in a qualifying section. Count subarrays by their start and end indices, not by distinct sequences. Exactly k is different from at most k, and k is always positive. Worked example For [2, 1, 2] and k = 1, the qualifying sections are [1], [2, 1], [1, 2] and [2, 1, 2]. The count is 4.

Input format

First line: n k. Next line: n integers.

Output format

Print the number of qualifying subarrays.

Constraints

1 <= k <= n <= 50000; 1 <= values <= 100000; use a 64-bit count.

Sample input

3 1
2 1 2

Sample output

4