CSES - Datatähti 2017 loppu - Mex-luku
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Taulukon mex-luku on pienin epänegatiivinen kokonaisluku, jota ei ole taulukossa. Esimerkiksi taulukon [3,0,4,3,7,1][3,0,4,3,7,1] mex-luku on 22.

Tehtäväsi on laskea nn-alkioisen taulukon jokaisen kk-kokoisen alitaulukon mex-luku.

Syöte

Syötteen ensimmäisellä rivillä on luvut nn ja kk: taulukon koko ja alitaulukon koko.

Seuraavalla rivillä on nn lukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Tulosta nk+1n-k+1 lukua: jokaisen alitaulukon mex-luku. Käy läpi alitaulukot järjestyksessä vasemmalta oikealle.

Esimerkki

Syöte:

5 3
2 1 5 0 5

Tuloste:

0 2 1

Selitys: Alitaulukot ovat [2,1,5][2,1,5], [1,5,0][1,5,0] ja [5,0,5][5,0,5].

Osatehtävä 1 (28 pistettä)

  • 1kn1001 \le k \le n \le 100
  • 0xi1090 \le x_i \le 10^9

Osatehtävä 2 (72 pistettä)

  • 1kn1051 \le k \le n \le 10^5
  • 0xi1090 \le x_i \le 10^9