1022 : Count Different Numbers I

Description

Given a series of n numbers, and a width w. Find the total number of different numbers of all consecutive w numbers.

For example: the numbers are {2, 2, 1, 3, 4, 4, 5} and w is 3. All the consecutive w numbers are:

{2, 2, 1}, 2 different numbers 2 and 1;
{2, 1, 3}, 3 different numbers 2, 1 and 3;
{1, 3, 4}, 3 different numbers …
{3, 4, 4}, 2 different numbers …
{4, 4, 5}, 2 different numbers …

The answer is 2 + 3 + 3 + 2 + 2 == 12.

Input

There are no more than 100 test cases. Each case contains two lines.

The first line has two integer numbers n and w.

The second line are n integer numbers.

1 <= w <= n <= 10^4.

All the n integer numbers are in range [1, 10^4].

Output

Give the total number of different numbers of all consecutive w numbers for each case.

Sample

7 2
2 2 1 3 4 4 5
7 3
2 2 1 3 4 4 5
7 7
2 2 1 3 4 4 5

10
12
5

Hint

Be careful that bruteforce could cause Time Limit Exceed

Source

Author

CSGrandeur