CSES - Datatähti 2019 alku - Taulukko
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Annettuna on taulukko, jossa on $n$ lukua. Monessako taulukon yhtenäisessä osataulukossa on enintään $k$ eri lukua?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: taulukon koko ja suurin sallittu määrä eri lukuja osataulukossa.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: taulukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus.

Esimerkki 1

Syöte:
5 2
1 2 3 1 1


Tuloste:
10

Esimerkki 2

Syöte:
8 1
1 1 1 1 1 1 1 1


Tuloste:
36

Osatehtävä 1 (12 pistettä)
  • $1 \le k \le n \le 100$
  • $1 \le x_i \le 10$
Osatehtävä 2 (35 pistettä)
  • $1 \le k \le n \le 5000$
  • $1 \le x_i \le 10^6$
Osatehtävä 3 (18 pistettä)
  • $1 \le k \le n \le 5 \cdot 10^5$
  • $1 \le k \le 2$
  • $1 \le x_i \le 10^9$
Osatehtävä 4 (35 pistettä)
  • $1 \le k \le n \le 5 \cdot 10^5$
  • $1 \le x_i \le 10^9$