Kiểm thử độ ổn định

Trong quá trình kiểm thử phần mềm tự động, đội ngũ kỹ sư cần đánh giá độ ổn định của một dịch vụ mạng. Hệ thống đã ghi nhận lại ~N~ chỉ số độ trễ của ~N~ yêu cầu kiểm thử liên tiếp, được biểu diễn bằng dãy số nguyên ~A_1, A_2, \dots, A_N~.

Một đợt kiểm thử được xem là ổn định nếu nó gồm một chuỗi các yêu cầu liên tiếp từ vị trí ~l~ đến vị trí ~r~ (~1 \le l \le r \le N~) thỏa mãn độ chênh lệch giữa độ trễ lớn nhất và độ trễ nhỏ nhất trong đoạn đó không vượt quá ngưỡng cho phép ~K~, tức là:

Hãy giúp các kỹ sư đếm số lượng đợt kiểm thử ổn định (tức số cặp chỉ số ~(l, r)~ với ~1 \le l \le r \le N~ thỏa mãn điều kiện trên).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 2 \times 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~ (~0 \le A_i \le 10^9~).

Dữ liệu ra

• In ra một số nguyên duy nhất là số lượng đợt kiểm thử ổn định.

Ràng buộc

• ~1 \le N \le 2 \times 10^5~
• ~0 \le K \le 10^9~
• ~0 \le A_i \le 10^9~
• Subtask 1 (40% số điểm): ~N \le 2000~
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm

Ví dụ

Ví dụ 1:

5 2
1 3 2 5 4

Đầu ra:

9

Ví dụ 2:

4 0
3 3 3 3

Đầu ra:

10

Gợi ý

• Khi mở rộng một đoạn sang phải, giá trị lớn nhất không giảm và giá trị nhỏ nhất không tăng. Do đó, nếu đoạn ~[l, r]~ thỏa mãn điều kiện thì mọi đoạn con ~[l', r]~ với ~l \le l' \le r~ cũng thỏa mãn.
• Sử dụng kỹ thuật hai con trỏ kết hợp hai hàng đợi hai đầu (monotonic deque) để tìm giá trị ~l~ nhỏ nhất cho mỗi ~r~ trong thời gian ~O(N)~.