Đoạn con có k số bằng nhau

Cho một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ và một số nguyên dương $k$.

Một đoạn con $a[i\dots j]$ (với $1\le i\le j\le n$) là dãy các phần tử liên tiếp $a_i,a_{i+1},\dots ,a_j$.

Hãy đếm số đoạn con của dãy $a$ mà trong đó có ít nhất $k$ phần tử mang cùng một giá trị. Nói cách khác, đoạn con $a[i\dots j]$ được tính nếu tồn tại một giá trị $v$ xuất hiện không dưới $k$ lần trong $a_i,a_{i+1},\dots ,a_j$.

Hai đoạn con được coi là khác nhau nếu cặp chỉ số $(i,j)$ của chúng khác nhau, kể cả khi nội dung giống hệt nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất: số đoạn con thoả mãn.

Ràng buộc

• $1\le k\le n\le 4·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ