CSES - Datatähti 2021 alku - Alitaulukot
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Taulukossa on $n$ kokonaislukua. Monessako yhtenäisessä alitaulukossa suurimman ja pienimmän luvun ero on enintään $k$?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: taulukon koko ja suurin sallittu erotus.

Seuraavalla rivillä on $n$ lukua $x_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]$, $[1]$, $[2]$, $[6]$, $[4]$, $[3,1]$, $[1,2]$, $[6,4]$ ja $[3,1,2]$.

Rajat

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

Osatehtävä 1 (11 pistettä)
  • $1 \le n \le 100$
Osatehtävä 2 (26 pistettä)
  • $1 \le n \le 2000$
Osatehtävä 3 (63 pistettä)
  • $1 \le n \le 10^5$