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 dương ai 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 ≤ k ≤ 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.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên dương $n, k (1 ≤ k ≤ n ≤ 4× 10^5)$
• Dòng thứ 2 chứa n số nguyên dương $a_1, a_2,…, a_n (1≤a_i≤10^6)$ Các số trên một dòng cách nhau bởi một dấu cách trống.

Kết quả: Ghi một số nguyên dương thỏa mãn yêu cầu bài toán.

Ví dụ:

Input

5  2 
1  2  1  2  1 

Output

6 

Giải thích

Có 6 dãy:

1 2 1; 1 2 1 2; 1 2 1 2 1; 2 1 2; 2 1 2 1; 1 2 1 thỏa mãn có ít nhất 2 sản phẩm cùng mã loại.

Giới hạn:

• 40% số test với $1≤n≤10^3$
• 40% số test với $10^3<n≤10^4$
• 20% số test với $104< n≤4×10^5$