Cho số nguyên dương \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\) và số nguyên \(k\). Ta gọi dãy con gồm các số hạng liên tiếp \(a_i,a_{i+1},…,a_j\) là một dãy đẹp nếu:

• Dãy con \(a_i,a_{i+1},…,a_j\) có ít nhất một số chẵn và có ít nhất một số lẻ.

• Gọi \(x\) là tổng các số hạng chẵn, \(y\) là tổng các số hạng lẻ trong dãy con \(a_i,a_{i+1},…,a_j\) thì \(0≤x-y≤k.\)

Yêu cầu: Tìm số lượng dãy con gồm các số hạng liên tiếp trong dãy \(a\) là dãy số đẹp.

Input

• Dòng 1 chứa 2 số nguyên \(n, k.\)

• Dòng thứ 2 chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n (1≤a_i≤10^6 ).\)

Output

• Ghi một số nguyên dương là số lượng dãy con của dãy \(a\) là dãy đẹp.

Ràng buộc

• Subtask 1: 40% test với \(1≤n≤200;0≤k≤10^6.\)

• Subtask 2: \(200<n≤2000;0≤k≤10^6.\)

• Subtask 3: \(2000<n≤2*10^5;k=0.\)

• Subtask 4: \(2000<n≤2000;1≤k≤10^3.\)

Sample Input

5 5
1 3 2 9 10

Sample Output

3

Sample Input

5 3
1 1 1 1 20

Sample Output

0