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 ~a_i~ là loại mã tương ứng (các sản phẩm giống nhau thì có cùng một loại mã). 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~ thoả mãn có ít nhất ~k~ sản phẩm cùng mã loại ~(1 \le k \le n)~, với dãy con là dãy được tạo từ các phần tử liên tiếp của ~A~.

Bạn hãy viết chương trình giúp 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 đầu vào

Gồm hai dòng:

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

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

Dữ liệu đầu ra

Gồm một dòng chứa một số nguyên dương thoả mãn yêu cầu bài toán.

Ràng buộc dữ liệu

• 40% số text với ~1 \le n \le 10^3~;
• 40% số text với ~10^3 < n \le 10^4~;
• 20% số text với ~10^4 < n \le 4 \times 10^5~.

Ví dụ

Ví dụ 1

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~ thoả mãn có ít nhất hai sản phẩm cùng mã loại.