Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Duomenų failas: bokstai2.in

Rezultatų failas: bokstai2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Bokštai

Mieste yra N į vieną eilę išrikiuotų bokštų. i-tojo bokšto aukštis yra H_i. Miesto meras nutarė perstatyti miestą ir padaryti jį gražų. Miestas yra gražus, jei visi bokštai yra surikiuoti ne mažėjimo tvarka iš kairės į dešinę.

Miesto perstatymas vyksta darant kelias (galbūt 0) operacijų.

Operacija vyksta taip: kranas pakelia kurį nors bokštą ir uždedą jį ant kurio nors gretimo bokšto. Tai yra, mes galima paimti i-tąjį bokštą ir jį uždėti ant i+1 arba i-1 bokšto. Naujo bokšto aukštis yra lygus dviejų panaudotų bokštų sumai. Tai reiškia, jog po kiekvienos operacijos bokštų skaičius sumažėja vienetu.

Padėkite merui sužinoti minimalų operacijų skaičių padaryti miestą gražų.

Pradiniai duomenys

Pirmoje eilutėje skaičius N (1\\leqN\\leq5000) - bokštų skaičius.

Antroje eilutėje yra N skaičių H_i (1\\leqH_i\\leq10^5) - i-tojo bokšto aukštis.

Rezultatai

Išveskite vieną skaičių - kiek minimaliai operacijų reikia atlikti.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
8 2 7 3 1
 
3