(Ở một tương lai xa xôi) Trên con đường mới được quy hoạch của thành phố X, có \(n\) tòa nhà cao tầng nằm trên một con đường (tạm coi như một đường thẳng). Nhà thứ \(i\) có độ cao là \(h_i\) mét.
Việt không thích những tòa nhà có cùng độ cao nằm gần nhau. Cậu định nghĩa một dãy nhà \([l,r] (l\le r)\) là "nhàm chán" nếu như trong toàn bộ những căn nhà thứ \(l,l+1,l+2,\dots,r-1,r\) chỉ có không quá \(k\) độ cao khác nhau.
Nhằm đánh giá con đường này, Việt cần tính số lượng dãy nhà nhàm chán. Vì đã thấm mệt sau khi đi từ đầu đường tới cuối đường để lấy thông tin về chiều cao của các tòa nhà, Việt nhờ bạn lập trình giải quyết vấn đề trên. Hãy giúp Việt nhé!
Bonus: sau khi hỏi thị trưởng, Việt đã có được một số thông tin giúp việc tính toán trở nên dễ dàng hơn. Thông tin này được kí hiệu bởi số \(\theta\)

Input

• Dòng đầu tiên chứa \(\theta\) \((\theta \in \{1,2,3,4,5\})\): thông tin mới có được từ thị trưởng
• Dòng thứ hai chứa \(n,k\) \((1 \le n,k \le 10^5)\): số tòa nhà, và số định nghĩa sự "nhàm chán"
• Dòng tiếp theo chứa \(n\) số nguyên dương \(h_1, h_2, h_3, \dots, h_n (1 \le h_i \le 10^9)\)

Output

• Dòng duy nhất chứa số dãy nhà nhàm chán mà bạn đếm được

Scoring

• Subtask 1 (\(20\%\) số điểm): \(\theta = 1, h_i \le n \le 100\)
• Subtask 2 (\(30\%\) số điểm): \(\theta = 2, h_i \le n \le 1000\)
• Subtask 3 (\(15\%\) số điểm): \(\theta = 3\) và các tòa nhà có chiều cao khác nhau đôi một.
• Subtask 4 (\(15\%\) số điểm): \(\theta = 4, k = 1\)
• Subtask 5 (\(20\%\) số điểm): \(\theta = 5\), không có ràng buộc gì thêm.

1
5 2
1 2 3 1 1

10