408850: GYM103348 L Army Composition

King Henry V is marching out to war against the French with his fierce and valiant army! He has $$$n$$$ soldiers that are standing together side to side in a line, and he wishes to take contiguous subarrays of these soldiers to form attack squadrons and effectively lead his army into war.

Each of the $$$n$$$ soldiers has a Duke that they pledge fealty to, given by a specific type, $$$t_i$$$. If two soldiers share the same $$$t_i$$$ value, they pledge fealty to the same Duke. To avoid potential rebellion, King Henry wants to avoid picking a squadron that has over $$$k$$$ soldiers that pledge fealty to the same Duke. Also, to ensure each attack squadron has sufficient camaraderie, if there exists some soldier in the squadron that pledges fealty to a specific Duke, there must exist $$$k$$$ soldiers that pledge fealty to that Duke so that each soldier has company. To summarize these constraints, there must be either $$$0$$$ soldiers that pledge fealty or $$$k$$$ soldiers that pledge fealty for any given Duke in a valid attack squadron.

Given these constraints, King Henry wants to know the number of possible attack squadrons that he can form successfully. Write a program to calculate the answer!

The first line consists of two integers $$$n$$$ and $$$k$$$ $$$(1 \leq k, n \leq 10^5)$$$. The next line consists of $$$n$$$ space separated integers $$$t_i$$$ $$$(1 \leq t_i \leq 10^5)$$$, which gives the ID of the Duke that the $$$i$$$th solider in line pledges fealty to.

Output a single integer giving the number of possible squadrons that King Henry V can form.

5 3
1 1 1 1 1

3

5 1
1 1 2 2 3

7

In the first sample, any subarray of size $$$3$$$ is valid.

In the second sample, all of the subarrays with a single element and the subarrays $$$[1, 2]$$$ and $$$[2, 3]$$$ will satisfy King Henry V's desired property.