Cho một mảng \(A\) gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một số nguyên không âm \(K\).

Một đoạn con liên tiếp \(A[l..r]\) (\(1 \le l \le r \le N\)) được gọi là hợp lệ nếu thỏa mãn đồng thời hai điều kiện sau:

1. Chênh lệch giữa giá trị lớn nhất và giá trị nhỏ nhất trong đoạn không vượt quá \(K\), tức là:

   \[ \max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) \le K \]

2. Số lượng phần tử phân biệt (khác nhau) trong đoạn \(A[l..r]\) là một số chẵn.

Hãy đếm số lượng đoạn con liên tiếp hợp lệ trong mảng \(A\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5\), \(0 \le K \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số lượng đoạn con liên tiếp hợp lệ.

Example

4 2
1 2 1 3

4

Scoring

• Subtask 1 (\(100\%\) số điểm): \(1 \le N \le 2 \cdot 10^5\), \(0 \le K \le 10^9\), \(1 \le A_i \le 10^9\).