Se consideră un șir de N numere ce reprezintă numărul de bomboane din N punguțe așezate în linie. Georgel pornește din dreptul primei punguțe și ia din ea o bomboană, apoi trece la următoarea și ia din ea două bomboane și continuă în acest fel luând de fiecare data cu o bomboană mai mult decât a luat din punga precedentă. Dacă au mai rămas bomboane în punguțe astfel încât el să mai poată face o tură completă, continuă să ia bomboane, câte una în plus față de punguța din care a luat anterior. Dacă nu mai sunt bomboane, se oprește și își numără bomboanele adunate în total.

Cerința

Cunoscându-se numărul N de punguțe și numărul de bomboane din fiecare punguță, să se stabilească numărul de bomboane pe care le va aduna Georgel.

Date de intrare

Din fișierul bomboane2.in se citesc, de pe prima linie numărul N de punguțe, iar de pe linia a doua, N numere naturale reprezentând numărul de bomboane din fiecare punguță, în ordinea în care se află. Numerele sunt despărțite între ele prin spații.

Date de ieșire

În fișierul bomboane2.out se afișează valoarea M, reprezentând numărul de bomboane pe care le poate aduna Georgel.

Restricții și precizări

• 1 ≤ N ≤ 100000
• Numărul bomboane din fiecare punguță este un număr natural nenul mai mic decât 1012.

Exemplu:

bomboane2.in

6
180 90 141 55 63 120

bomboane2.out

300

Explicație

Georgel pornește de la punguța numărul 1 şi ia o bomboană, din a doua ia două bomboane, din a treia 3 bomboane, din a patra 4, din a cincea 5, din a șasea 6; la următoarea tură ia din prima 7 bomboane, din a doua 8, din a treia 9, din a patra 10 și în continuare 11, 12; la următoarea tura ia 13, 14, 15, 16 17, 18, iar la a patra tură ia 19, 20, 21, 22, 23, 24 bomboane. La a cincea tură se oprește deoarece în unele punguțe nu se mai află numărul de bomboane necesar pentru a termina o nouă tură completă. Astfel adună în total 300 de bomboane.