Thống kê sản phẩm

Anh An là nhân viên kỹ thuật trong nhà máy X trên địa bàn tỉnh. Nhà máy được trang
bị dây chuyền sản xuất hiện đại, tất cả các sản phẩm khi đi qua băng chuyền được máy tính
đánh mã loại và lưu lại. Sản phẩm thứ i đi qua băng chuyền được gán bởi một số nguyên
đương \(a_{i}\) là mã loại tương ứng (các sản phẩm giống nhau thì có cùng một mã loại). Trong
một công đoạn sản xuất, có \(n\) sản phẩm đi qua băng chuyền được máy tính đánh mã loại và
lưu lại thành một dãy \(A\) gồm các số nguyên dương \(a_{1}, a_{2}, ...,a_n\). Kết thúc công đoạn, lãnh
đạo công ty yêu cầu anh An báo cáo số lượng tất cả các dãy con của dãy \(A\) thỏa mãn có ít
nhất \(k\) sản phẩm cùng mã loại \((1 \leq k \leq n)\), với dãy con là dãy được tạo từ các phần tử liên
tiếp của dãy \(A\).

Bạn hãy viết chương trình giúp anh An giải quyết bài toán trên.

Yêu cầu: Đưa ra số lượng tất cả các dãy con của dãy \(A\) có ít nhất \(k\) sản phẩm cùng mã loại.

Input

Từ tệp văn bản TKSP.INP gồm:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n, k\) \((1 \leq k \leq n \leq 4 \times 10^5)\)
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, ...,a_n (1 \leq a \leq 10^6)\)

Các số trên một dòng cách nhau bởi một dấu cách trống.

Output

Ghi ra tệp văn bản TKSP.OUT gồm một dòng chứa một số nguyên dương
thỏa mãn yêu câu bài toán.

Example

5 2
1 2 1 2 1

6

Scoring

• \(40\%\) số test với \(1 \leq n \leq 10^3\)
• \(40\%\) số test với \(10^3 < n \leq 10^4\)
• \(20\%\) số test với \(10^4 < n \leq 4 \times 10^5\)