# Arhitekt

Arhitekt Ahac se je znašel pred težko nalogo. Mestni svetniki so ga izbrali za vodjo prenove Ahilove avenije. Do sedaj so zgradbe gradili po potrebi, kar je precej skazilo izgled avenije, sedaj pa so se odločili, da bodo nekaterim zgradbam vzeli nekaj nadstropij, nekaj zgradb pa bodo dogradili tako, da se bosta dve sosednji zgradbi po višini razlikovali za največ $H$.

$N$ zgradb ob aveniji opišemo kot polje $S$, kjer $S[i]$ predstavlja višino (število nadstropij) $i$-te zgradbe. Tvoja naloga je, da Ahacu poveš, koliko nadstropij zgradb bo potrebno porušiti ali zgraditi, da na koncu velja $|S[i] - S[i+1]| \leq H$ za vsak $1 \leq i \leq N-1$.

## Vhod

V prvi vrstici standardnega vhoda se nahajata naravni števili $N$ in $H$.

V drugi vrstici standardnega vhoda se nahaja $N$ nenegativnih celih števil, kjer $i$-to število predstavlja višino $i$-te zgradbe.

## Izhod

Na standardni izhod izpiši eno celo število - najmanjše število vseh delov zgradb, ki jih je potrebno porušiti ali dograditi.

## Podnaloge

Za vse testne primere velja:

- $1 \leq N \leq 200000$
- $0 \leq H \leq 10^9$
- $0 \leq S[i] \leq 10^9$, za vsak $1 \leq i \leq N$

1. podnaloga (6 točke): $N \leq 10$, $S[i] \leq 4$
2. podnaloga (9 točke): $N \leq 14$, $H \leq 1$, $S[i] \leq 4$
3. podnaloga (13 točk): $N \leq 10$, $H \leq 2$
4. podnaloga (7 točk): $H = 0$
5. podnaloga (8 točk): $N \leq 500$, $S[i] \leq 400$
6. podnaloga (11 točk): $N \leq 500$, $S[i] \leq 5000$
7. podnaloga (11 točk): $N \leq 5000$, $S[i] \leq 5000$
8. podnaloga (16 točk): $N \leq 5000$
9. podnaloga (19 točk): Ni dodatnih omejitev

## Primeri

### 1. primer

(primer je veljaven za podnaloge 3, 5-9)

Vhod:

6 1
2 10 0 2 4 3

Izhod:

10

Komentar:


Zgornja slika predstavlja eno izmed možnih rešitev primera. Na levi strani je začetna postavitev, na desni pa končni izgled avenije.

Ta predelava mesta zahteva 10 potez. 7 delov zgradb je treba porušiti, 3 pa dograditi.

### 2. primer

(primer je veljaven za podnaloge 5-9)

Vhod:

6 3
2 10 2 6 4 3

Izhod:

6

Komentar:


### 3. primer

(primer je veljaven za podnaloge 1-3, 5-9)

Vhod:

4 1
1 4 1 4

Izhod:

4

Komentar:


### 4. primer

(primer je veljaven za podnaloge 3, 5-9)

Vhod:

10 1
10 9 8 7 6 5 4 3 2 1

Izhod:

0

Komentar:


### 5. primer

(primer je veljaven za vse podnaloge)

Vhod:

3 0
1 1 3

Izhod:

2

Komentar: