Whisker Weave Fragments

Time limit: 2000 msMemory limit: 256 MB

Gats has arranged $N$ colored beads along a string. The color of the $i$ -th bead is $C_i$ .

He calls a contiguous fragment $[L,R]$ , where $1 \le L \le R \le N$ , clean-ended if all of the following conditions hold:

Exactly $K$ distinct colors occur among $C_L, C_{L+1}, \ldots, C_R$ .

For a fragment consisting of one bead, that bead is considered both endpoints and its color occurs once.

Count the number of clean-ended fragments.

Input

The first line contains two integers $N$ and $K$ ( $1 \le K \le N \le 2 \times 10^5$ ), the number of beads and the required number of distinct colors.

Output

Print one integer: the number of clean-ended fragments.

Samples

Sample 1

Input

7 3
1 2 1 3 2 4 3

Output

The four qualifying fragments have endpoint pairs $[2,4]$ , $[3,5]$ , $[4,6]$ , and $[5,7]$ .

Whisker Weave Fragments

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2