635. Count Number of Nice Subarrays

0

Medium

You have a fondness for subarrays that contain exactly **k** odd numbers, which are referred to as ***Nice subarrays***. Given an array of integers nums and an integer **k**, a continuous subarray is considered nice if it contains k odd numbers. Determine the total number of nice subarrays.

Input Format

The first line contains two space-separated integers **N** (the size of the array) and **k**. The second line contains the integer array.

Output Format

Print the total number of nice subarrays.

Example

Input

5 3
1 1 2 1 1

Output

2

Constraints

1 <= N <= 5*10^4
1 <= K <= N
1 <= Nums[i] <= 10^5

Loading...

View Submissions

Console