copaci3

Copaci 3

== include(page="template/taskheader" task_id="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.

Badea Ion 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 pomii lui sunt foarte inestetici. Pentru asta, se gandeste sa imprumute bagheta magica pe care o foloseste Badea Gheorghe pentru a mari, respectiv a micsora lucruri pentru a isi infrumuseta pomi. Pomii au fost plantati in linie si fiecare pom are o inaltime de $X{~i~}$ metri. Badea Ion considera ca pomii 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.

h2. 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.

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 pomii sa indeplineasca conditia de mai sus.

h2. 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.

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.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ N ≤ 100$

* $1 ≤ D ≤ 10^9^$
* $1 ≤ X{~i~} ≤ 10^9^$

* $0 ≤ D ≤ 10^9^$
* $0 ≤ X{~i~} ≤ 10^9^$
* In caz ca nu se poate ajunge la o configuratie estetica se va afisa -1
* Badea Ion va recomanda sa folositi numere intregi pe 64 de biti pentru a calcula rezultatul

h2. Exemplu

h3. Explicaţie

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

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

== include(page="template/taskfooter" task_id="copaci3") ==

4084