Bài toán: Đếm số đoạn con có tối đa ~ k ~ giá trị khác nhau

Đề bài

Cho một mảng gồm ~ n ~ số nguyên và một số ~ k ~. Nhiệm vụ của bạn là đếm số đoạn con (subarray) có tối đa ~ k ~ giá trị khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ (kích thước mảng) và ~ k ~ (số giá trị khác nhau tối đa).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các phần tử của mảng.

Output

• In ra một số nguyên: số lượng đoạn con thỏa mãn điều kiện.

Ràng buộc

• ~ 1 \leq k \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq x_i \leq 10^9 ~

Ví dụ

Input:

5 2
1 2 3 1 1

Output:

10

Giải thích:

• Các đoạn con hợp lệ: ~ [1], [2], [3], [1], [1], [1, 2], [2, 3], [3, 1], [1, 1], [1, 3, 1] ~.