Đếm cặp

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.