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$