Fişierul intrare/ieşire:	copaci3.in, copaci3.out	Sursă	Summer Challenge 2009, Runda 3
Autor	Din Folclor	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Copaci3

Badea Ion vrea si-a cumparat de curand un teren pe care a plantat niste pomi. Obosit insa satisfacut dupa o zi intreaga de plantat pomi, Badea Ion s-a asezat frumos pe prispa sa isi admire munca. Stand acolo si uitandu-se la pomi, el observa ca pomi lui sunt foarte inestetici. Pentru asta el se gandeste sa imprumute bagheta magica pe care o foloseste Badea Gheorge pentru a mari respectiv a micsora lucruri pentru a isi infrumuseta pomi. Pomi au fost plantati in linie si fiecare pom are o inaltime de X_i metri. Badea Ion considera ca pomi sunt estetici daca si numai daca nu exista doi pomi consecutivi intre care diferenta de inaltime sa fie mai mare decat D. Folosind bagheta magica, el poate sa micsoreze sau sa mareasca inaltimea unui pom cu 1 metru printr-o singura atingere. De asemenea primul si ultimul pom au fost plantati de nepotii lui Badea Ion si nu vrea ca acestia sa fie modificati.

Cerinta

Fiind obosit atat din punct de vedere fizic cat si psihic Badea Ion va cere ajutorul si va intreaba care este numarul minim de atingeri necesare pentru ca pomi sa indeplineasca conditia de mai sus.

Date de intrare

Pe prima linie a fisierului copaci3.in se afla 2 numere, N si D, reprezentand numarul de pomi respectiv diferenta maxima de inaltime dintre 2 pomi pentru ca acestia sa nu fie inestetici. Pe urmatoarea linie se dau in ordine inaltimile celor N pomi.

Date de ieşire

In fisierul copaci3.out se va afisa un singur numar reprezentand numarul minim de atingeri cu bagheta pe care trebuie sa le efectueze Badea Ion.

Restricţii

• 1 ≤ N ≤ 100
• 1 ≤ D ≤ 10⁹
• 1 ≤ X_i ≤ 10⁹

Exemplu

Explicaţie

Pomul 2 este micsorat cu 2 metri iar pomul 3 este marit cu 1 metru.

Cum se trimit solutii?