Rezolvare PBinfo #4427

Fie un șir de n numere naturale v[1], v[2], …, v[n], unde v[i] reprezintă al i-lea număr din șir. O subsecvență [x, y] a șirului v (cu 1 ≤ x ≤ y ≤ n) conține toate elementele v[x], v[x+1], ..., v[y - 1], v[y].

Cerința

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], …, 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 ≤ n ≤ 1.000.000
• 1 ≤ k ≤ 5
• 1 ≤ v[i] ≤ 1.000.000.000, pentru 1 ≤ i ≤ 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].