Cho dãy a gồm n số nguyên dương ~a_1,a_2,a_3 ,..., a_n~ và số nguyên k.Ta gọi dãy con gồm các số hạng ở vị trí liên tiếp ~a_i~ , ~a_i~~ _+~~_1~ , ~a_i~ ~_+~ ~_2~... + ~a_j~ là dãy đẹp nếu thỏa:

-Trong dãy có ít nhất một số lẻ và một số chẳn

-Gọi x là tổng chẵn,y là tổng lẻ thì 0 <= x - y <= k

Yêu cầu: Tìm số lượng dãy con liên tiếp của dãy a

Input

• Dòng 1 số nguyên n và k ~(2 ≤ k ≤ 2 * 10^5)~

  • Dòng 2 dãy n số số nguyên ~a_1,a_2,a_3,...,a_n.~

Output

Số lượng dãy liên tiếp đẹp

Giới hạn

• 40% test ~ 1 ≤ n ≤ 200~, ~0 ≤ k ≤ 10^6~

• 30% test ~ 200 ≤ n ≤ 2000~, ~0 ≤ k ≤ 10^6~

• 30% test ~ 200 < n ≤ 2 * 10^5~, ~k = 0~

• 10% test ~ 200 ≤ n ≤ 20000~, ~0 < k ≤ 100~

Ví dụ

Sample input

5 5
1 3 2 9 10

Sample output

3