Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\) và một số nguyên \(K\).

Yêu cầu: Đếm số cặp số \(L, R\) (\(1 \leq L \leq R \leq N\)) sao cho dãy con liên tiếp \(A_L, A_{L + 1}, \ldots, A_R\) có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá \(K\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, K\) (\(N \leq 10^5, K \leq 10^{18}\)).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) (\(|A_i| \leq 10^9\)).

Output

• In ra một số nguyên duy nhất là kết quả của bài toán.

Example

5 2
2 -1 3 1 3

8

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 5000\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.