Problem 1204: gaina

Găina Chucky $767$ trebuie să străbată curtea sărind de pe un coteţ pe altul, sau zburând peste coteţe, de la primul la ultimul coteţ. Coteţele sunt reprezentate prin nişte dreptunghiuri de lăţime $1 \ m$ şi înălţimi date şi sunt numerotate în ordine de la stânga cu numerele de $1$ la $n$ . Două coteţe cu numere consecutive sunt lipite (adiacente). Iniţial, Chucky are un număr de unităţi de energie. Dacă la un moment dat Chucky ajunge să aibă energie strict negativă sau se află în imposibilitatea de a mai face un pas (întâlneşte un coteţ mai înalt decât cota la care se află), atunci nu mai poate continua acel drum.

Chucky poate să se deplaseze făcând următoarele tipuri de mişcări:

Pas. Găina păşeşte pe orizontală de pe un coteţ de înălţime $H$ pe următorul coteţ de aceeaşi înălţime (în desen: de la poziţia $h$ la $i$ ). În acest caz nu se pierde şi nu se câştigă energie.
Aterizare. Găina aterizează pe un coteţ de înălţime $H$ , venind în zbor, tot de la înălţimea $H$ (exemplu în desen: de la $g$ la $h$ ). Nici în acest caz nu se pierde şi nu se câştigă energie.
Decolare. Găina zboară $1 \ m$ pe orizontală de pe un coteţ (exemplu în desen de la $x$ la $a$ ). În acest caz găina pierde o unitate de energie.
Zbor orizontal. Găina zboară pe orizontală (exemplu în desen, de la $a$ la $b$ , de la $b$ la $c$ , $\dots$ ). În acest caz pierde câte o unitate de energie pentru fiecare metru parcurs pe orizontală.
Picaj. Găina coboară pe verticală (exemplu în desen de la $a$ la $d$ , sau de la $d$ la $g$ ). În acest caz câştigă câte o unitate de energie pentru fiecare metru coborât.

Mai jos, avem un drum format din $4$ coteţe, de înălţimi $4$ , $1$ , $2$ , $2$ . Exemplificăm diferite tipuri de mişcări din poziţia $x$ (ceea ce nu reprezintă un traseu complet):

Cerinţă

Să se determine energia minimă (un număr natural) pe care trebuie să o aibă Chucky la începutul călătoriei (când se află pe primul coteţ), astfel încât ea să poată ajunge pe coteţul $n$ , având în fiecare moment energia mai mare sau egală cu $0$ .

Date de intrare

Fişierul de intrare gaina.in conţine două linii. Pe prima linie se află numărul natural $n$ . Pe linia a doua se află $n$ numere naturale $h_1$ , $h_2$ , $\dots$ , $h_n$ (unde $h_i$ reprezintă înălţimea coteţului $i$ ), separate de câte un spaţiu.

Date de ieşire

Fişierul de ieşire gaina.out conţine o singură linie pe care se află un număr natural $K$ reprezentând energia minimă iniţială cu care găina Chucky poate să ajungă la coteţul $n$ , având în fiecare moment energia mai mare sau egală cu $0$ .

Restricții și precizări

$0 < n < 10 \ 001$
$0 \leq h_i \leq 30 \ 000$
Pentru datele de test există întotdeauna soluţie (primul coteţ are înălţimea mai mare sau egală cu înălţimea oricărui alt coteţ).

Exemplul 1

gaina.in

3
2 2 0

gaina.out

Exemplul 2