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