Anul trecut de ziua ta ai primit un șir de n
numere întregi. Anul acesta ai noroc: pe lângă un șir de numere întregi a
1
, a
2
, …, a
n
mai primești și un număr natural k
. Numim cadoul unei secvențe din șir de lungime k
numărul elementelor care apar o singură dată în secvență. De exemplu, dacă a=(1,2,1,3,5)
și k=4
, atunci cadoul secvenței (1,2,1,3)
este 2
(numerele 2
și 3
apar o singură dată), iar cadoul secvenței (2,1,3,5)
este 4
.
Cerința
Trebuie să determini suma cadourilor tuturor secvențelor de lungime k
din șir și vei mai primi cadou două bilete la teatru și o carte motivațională.
Date de intrare
Programul citește de la tastatură numerele naturale n
și k
, iar apoi n
numere naturale, separate prin spații, reprezentând șirul.
Date de ieșire
Programul va afișa pe ecran numărul C
, reprezentând suma cadourilor tuturor secvențelor.
Restricții și precizări
5 ≤ n ≤ 123.456
1 ≤ k ≤ n
-1.000.000.000 ≤ a
i
≤ 1.000.000.000
Exemplu:
Intrare
7 4 1 2 3 3 3 3 4
Ieșire
4
Explicație
Prima secvență de lungime 4
este (1,2,3,3)
și are cadoul egal cu 2
.
A doua secvență de lungime 4
este (2,3,3,3)
și are cadoul egal cu 1
.
A treia secvență de lungime 4
este (3,3,3,3)
și are cadoul egal cu 0
.
A patra secvență de lungime 4
este (3,3,3,4)
și are cadoul egal cu 1
.
Suma cadourilor este deci 4
.