409325: GYM103485 G The Diversity of the Library of Alexandria

One of the great legacies of Alexander the great was the cultural diffusion that he generated. He founded more than twenty cities that bore his name, most notably Alexandria in Egypt. One of the greatest libraries of antiquity was built in it, the library of Alexandria.

Arthur, a great intellectual and disciple of Aristotle, as well as Alexander, on one of his great trips, decides to visit the library and test its greatness. Once there, he is greeted by Renzo, the wise, who is a frequent visitor and knowledgeable about the collection. Then he makes the following challenge to Renzo:

- I know the magnitude of your library. I heard that it houses between thirty thousand and seven hundred thousand volumes. But I want to know whether it is really diverse. So show me a row of its best books and I want to see if it has an adequate diversity.

Renzo, the wise, confident begins to speak:

- But that's simple...

To which Arthur interrupts:

- Hang on! I haven't told you the details yet. Given this row that you will show me, I'll make things more interesting. I want to know how many ranges of consecutive books have exactly $$$k$$$ distinct books, where $$$k$$$ is a number that I find suitable to test the library.

Now you must help Renzo find that value. Each book is identified by an integer.

The first line contains two integers $$$n$$$ and $$$k$$$ — the number of books in the row to be analyzed and the number that is given by Arthur to Renzo to test the diversity of the library.

The next line contains $$$n$$$ integers $$$x_0, x_1, x_2, \dotsc, x_{n - 1}$$$ separated by a space identifying the books that appear in the row. A repeated number means a book repeated in the row.

Constraints

• $$$1 \leq n \leq 10^{6}$$$,
• $$$1 \leq k \leq n$$$ and
• $$$-10^{9} \leq x_i \leq 10^9$$$ for each $$$i \in \{0, 1, 2, \dotsc, n - 1\}$$$.

For the given row of $$$n$$$ books, answer how many ranges $$$[l, r]$$$ of books in it, with $$$l, r \in \{0, \dotsc, n - 1\}$$$, have exactly $$$k$$$ distinct books.

2 1
1 1

3

3 1
1 1 2

4

3 2
1 1 2

2

In the first test, the answer is $$$3$$$ since all possible ranges have exactly $$$1$$$ distinct book: $$$[0, 0]$$$; $$$[1, 1]$$$; $$$[0, 1]$$$.

In the second test, the ranges with exactly $$$1$$$ distinct book are all ranges of size $$$1$$$ plus the range $$$[0, 1]$$$, that is, $$$4$$$ in total.

In the third test, the ranges with exactly $$$2$$$ distinct books are just $$$[1, 2]$$$ and the entire range $$$[0, 2]$$$.