secvmin

Fie un șir de $n$ numere naturale $v_1$, $v_2$, $\dots$, $v_n$, unde $v_i$ reprezintă al $i$-lea număr din șir.
O subsecvență $[x, y]$ a șirului $v$ (cu $1 \leq x \leq y \leq n$) conține toate elementele $v_x, v_{x+1}, \dots, v_{y - 1}, v_y$.

Cerință

Fiind date două numere naturale $n$ și $k$ și un șir $v$ de $n$ numere naturale, scrieți un program care să răspundă la următoarea întrebare: câte subsecvențe conțin simultan cele mai mici $k$ valori distincte din șir?

Date de intrare

Fișierul de intrare secvmin.in conține pe prima linie numerele $n$ și $k$, iar pe cea de a doua linie se vor afla numerele naturale $v_1$, $v_2, \dots, v_n$, cu semnificația din enunț. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire secvmin.out va conține o singură linie pe care va fi scris răspunsul la cerința problemei.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$;
• $1 \leq k \leq 5$;
• $1 \leq v_i \leq 1 \ 000 \ 000 \ 000$, pentru $1 \leq i \leq n$;
• Se garantează că șirul va conține cel puțin $k$ valori distincte.

Exemplul 1

secvmin.in

7 1
1 3 2 2 1 3 2

secvmin.out

19

Explicație

$k=1$. Cea mai mică valoare din șir este egală cu $1$.
Subsecvențele care conțin valoarea 1 sunt: $[1, 1]$, $[1, 2]$, $[1, 3]$, $[1, 4]$, $[1, 5]$, $[1, 6]$, $[1, 7]$, $[2, 5]$, $[2, 6]$, $[2, 7]$, $[3, 5]$, $[3, 6]$, $[3, 7]$, $[4, 5]$, $[4, 6]$, $[4, 7]$, $[5, 5]$, $[5, 6]$, $[5, 7]$.

Exemplul 2

secvmin.in

7 2
1 5 2 2 1 5 2

secvmin.out

15

Explicație

$k=2$. Cea mai mică valoare din șir este egală cu $1$, iar a doua cea mai mică valoare din șir este egală cu $2$.
Subsecvențele care conțin valorile $1$ și $2$ sunt: $[1, 3]$, $[1, 4]$, $[1, 5]$, $[1, 6]$, $[1, 7]$, $[2, 5]$, $[2, 6]$, $[2, 7]$, $[3, 5]$, $[3, 6]$, $[3, 7]$, $[4, 5]$, $[4, 6]$, $[4, 7]$, $[5, 7]$.