Laiko ribojimas: 1s

Atminties ribojimas: 32MB

Jei norite pateikti savo sprendimą - prisijunkite.

Išsiliejęs vanduo

Robinzonas Kruzas ir vėl įstrigo negyvenamoje saloje. Šį kart jam ypatingai nepasisekė - negyvenamojoje saloje nėra gėlo vandens upelio, tad vienintelis būdas gauti vandens yra sulaukti lietaus. Gerai, kad sala yra ganėtai palankioje geografinėje pozicijoje ir lietus nėra retas.

Tad Robinzonui telieka viena problema - kaip lyjant lietui susirinkti kiek įmanoma daugiau vandens. Kadangi sudužęs Robinzono laivas plukdė žaislus, - jis turi beveik neišsenkamą lego kaladėlių šaltinį. Iš šių kaladėlių jis planuoja pasidaryti kibirėlį, kurį naudos vandens surinkimui.

Jūsų džiaugsmui, konstruoti optimalaus kibirėlio iš kaladėlių nereikės - tą padarė Robinzonas :) Jums tereiks atsakyti į klausimą: kiek maksimaliai vandens gali tilpti į jo sukonstruotą kibirėlį?

Kiekvieną kibirėlį Robinzonas atvaizduoja kaip pjūvį, kurį sudaro N skaičių. Iš šių skaičių a_i nusako, kiek i'tojoje pozicijoje yra vertikaliai sudėtų kaladėlių. Kitaip tariant, jei Robinzonas turi masyvą 1, 5, 2, 3, 8, 1, 9, tai jo kibirėlis atrodys taip:

      *
    * *
    * *
    * *
 *  * *
 *  * *
 * ** *
 **** *
*******

O pilnai užpildžius kibirėlį, jo pjūvis atrodytų taip:

      *
    *-*
    *-*
    *-*
 *--*-*
 *--*-*
 *-**-*
 ****-*
*******

Tad šiame pjūvyje telpa 12 vandens blokų - tai ir yra užduoties atsakymas

Pradiniai duomenys

Skaičius 0\\leqN\\leq1000000, nurodantis kibirėlio pjūvio plotą. Toliau seka eilutė, sudaryta iš skaičių a_1,a_2,\\ldots,a_N (0\\leqa_i\\leq1000000), aprašančių kibirėlio pjūvį.

Rezultatai

Maksimalus vandens blokų kiekis nurodytame pjūvyje.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
7
1 5 2 3 8 1 9
 
12