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$