Emergency task

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

After Zenyk had a delicious lunch, he received an unexpected call from his friend Marichka. Her voice sounded worried:

— Zenyk, help out! I have a serious problem.

— What happened?

— I work as an analyst at a company that researches unique data sequences. My boss gave me an urgent task: find the number of subarrays in an array where the number of unique numbers is at least \(k\). If I don’t finish by the end of the day, I might get fired!

— Calm down, Marichka. Explain it to me in more detail.

— I have an array of \(n\) integers. I need to find the number of subarrays where the number of unique elements is at least \(k\). A subarray is a contiguous sequence of elements in an array. Two subarrays are considered different if their starting or ending indices differ.

Zenyk quickly thought about the problem. For him, it was another puzzle that he solved instead of crosswords. But this time the stakes were too high — Marichka’s job!

Can you help Zenyk save his friend from being fired?

Input

The first line contains two integers \(n\) and \(k\) — the size of the array and the minimum number of unique elements in a subarray.

The second line contains \(n\) space-separated integers — the array \(a_i\).

Output

Print the number of subarrays of the given array that have at least \(k\) unique elements.

Constraints

\(1 \leq k \leq n \leq 2 \cdot 10^5\),

\(1 \leq a_i \leq 10^9\).

Grading consists of the following blocks:

• 1 point for each example from the statement,

• 10 points: \(n \le 100\),

• 20 points: \(n \le 1000\),

• 7 points: \(k=1, n \le 1000\),

• 13 points: \(k=1\),

• 47 points: no additional constraints.

You will get the points for a block only if your program passes all the tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 1 2 2 3 4 1 2	8

Input (stdin) сopy	Output (stdout) сopy
4 1 4 7 4 7	10

Input (stdin) сopy	Output (stdout) сopy
4 2 4 4 4 4	0

Notes

In the first example [2, 2, 3, 4, 1] is a subarray of the original array and the number of unique elements is 4. There are a total of 8 such subarrays.