ADDEVENB - Add To Even (Part B)

You are given a list of n positive integers a_1, a_2 ... a_n and an integer k.

Output the number of unique pairs of integers in the list such that that they add to an even number and the two numbers are at most k numbers away from each other in the list. i.e. the number of pairs (i, j) such that i < j, a_i + a_j is even and j - i ≤ k.

NOTE: Two pairs are unique to each other if and only if at least one of the indices of the numbers of the first pair is different to the second pair.

Input

Your first line will contain two space-separated integers n and k.

Your second line will contain n space-separated integers representing a_1, a_2 ... a_n

1 ≤ k < n ≤ 100,000

Output

Your first and only line of output should contain a single integer representing the number of unique pairs of integers with the even sum and are only k indices apart in the original list.

Example

Input 1
3 1
1 1 1

Output 1
2
Input 2
6 4
2 12 3 14 29 4

Output 2
6

Added by:jslew
Date:2021-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.