Se consideră un șir de N numere ce reprezintă cantitățile disponibile de produse de sezon de N tipuri, în ordinea în care acestea sunt aduse de la magazie. Un automat poate realiza pachete cu două dintre tipurile de produse venite una imediat după cealaltă de la magazie. El este programat să pună în fiecare pachet un același număr A de produse de un tip și un același număr B de produse de celălalt tip, astfel încât să nu rămână produse necuprinse în pachete.
De exemplu, dacă există 20 de prăjiturele COCO și 15 cutii de suc JUMBO, atunci automatul va fi programat să pună 4 prăjiturele și 3 sucuri în fiecare pachet, epuizând simultan stocul de prăjiturele și cutii de suc și obținând astfel 5 pachete. Pentru alte două tipuri de produse consecutive se va proceda la fel, schimbându-se doar parametrii A și B ale programului de împachetare.
La unele produse din șir se poate renunța în totalitate, nefiind incluse în niciun pachet.

Cerința

Cunoscându-se numărul N de tipuri de produse și cantitățile din fiecare produs, în ordinea în care sosesc de la magazie, să se stabilească numărul maxim de pachete care se pot obține prin alegerea convenabilă a perechilor de produse consecutive și programarea corespunzătoare a automatului, pentru fiecare pereche aleasă.

Date de intrare

Din fișierul pachete2.in se citesc, de pe prima linie numărul N de tipuri de produse, iar de pe linia a doua, N numere naturale reprezentând stocurile de produse de fiecare tip, în ordinea în care vin acestea de la magazie. Numerele sunt despărțite între ele prin spații.

Date de ieșire

În fișierul pachete2.out se afișează valoarea P reprezentând numărul maxim de pachete care se pot forma.

Restricții și precizări

• 1≤N≤100000
• Numărul de produse disponibile din fiecare tip este un număr natural nenul cu cel mult 6 cifre.
• Din orice produs din șir, mașina de împachetat poate fi programată să pună în fiecare pachet cel puțin unul și cel mult toate produsele disponibile.
• Numărul maxim de pachete obținut este cel mult 2000000000.
• După ultimul număr din fișier se pot afla unul sau mai multe spații.

Exemplu:

pachete2.in

5
20 15 18 12 13

6
18 9 5 14 63 2

pachete2.out

11

16

Explicație