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 dương \(a_i\) là mã loại tương ứng, trong một đ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, \dots, a_n\).

Kết thúc công đoạn sản xuất, 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, 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\).

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

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n, k\) \((1 \le k \le n \le 4 \cdot 10^5)\);

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^6)\).

Output

Ghi ra một số nguyên là kết quả của bài toán.

Notes

Với \(A = (1, 2, 1, 2, 1)\) và \(k = 2\), có \(6\) dãy con thỏa mãn:
\([1,2,1]\), \([1,2,1,2]\), \([1,2,1,2,1]\), \([2,1,2]\), \([2,1,2,1]\), \([1,2,1]\) (đoạn từ vị trí \(3\) đến \(5\)).

Scoring

• (40%) \(1 \le n \le 10^3\);

• (40%) \(10^3 < n \le 10^4\);

• (20%) \(10^4 < n \le 4 \cdot 10^5\).