Pracsiu Dan (dnprx) Aveți la dispoziție un șir a1, a2, …, an de numere naturale și k un număr natural. Pentru fiecare secvență de lungime k din vector trebuie să determinăm pe third, cea de-a treia cea mai mică valoare. De exemplu, secvența 3,6,1,3,7,4 are ca third pe 3, iar secvența 7,7,7,2,2,2,6 are ca third pe 2.
Cerința
Calculați suma valorilor third pentru toate secvențele de lungime k din șir.
Date de intrare
Fișierul de intrare third.in conține pe prima linie numerele n și k, iar pe a doua linie șirul de n numere naturale separate prin spații.
Date de ieșire
Fișierul de ieșire third.out va conține pe prima linie numărul S, reprezentând suma valorilor third a tuturor secvențelor de lungime k.
Restricții și precizări
4 ≤ n ≤ 100.0003 ≤ k ≤ n- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1.000.000.000
Exemplu:
third.in
10 5 4 4 4 2 9 8 1 5 6 3
third.out
28
Explicație
Prima secvență de lungime 5 este 4 4 4 2 9 și are ca third pe 4.
A doua secvență de lungime 5 este 4 4 2 9 8 și are ca third pe 4.
A treia secvență de lungime 5 este 4 2 9 8 1 și are ca third pe 4.
A patra secvență de lungime 5 este 2 9 8 1 5 și are ca third pe 5.
A cincea secvență de lungime 5 este 9 8 1 5 6 și are ca third pe 6.
Ultima secvență de lungime 5 este 8 1 5 6 3 și are ca third pe 5.
Suma valorilor third este 4+4+4+5+6+5=28.