CSES - Datatähti 2021 alku - Alitaulukot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Taulukossa on nn kokonaislukua. Monessako yhtenäisessä alitaulukossa suurimman ja pienimmän luvun ero on enintään kk?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja kk: taulukon koko ja suurin sallittu erotus.

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

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus.

Esimerkki

Syöte:

5 2
3 1 2 6 4

Tuloste:

9

Selitys: Alitaulukot ovat [3][3], [1][1], [2][2], [6][6], [4][4], [3,1][3,1], [1,2][1,2], [6,4][6,4] ja [3,1,2][3,1,2].

Rajat

Kaikissa testeissä 0k1090 \le k \le 10^9 ja 1xi1091 \le x_i \le 10^9.

Osatehtävä 1 (11 pistettä)

  • 1n1001 \le n \le 100

Osatehtävä 2 (26 pistettä)

  • 1n20001 \le n \le 2000

Osatehtävä 3 (63 pistettä)

  • 1n1051 \le n \le 10^5