Pentru a nu intra în faliment, noua conducere a fabricii OLDTRICK a derulat un plan de restructurate în n etape. În fiecare etapă, fabrica a împrumutat de la bancă o sumă ai. La terminarea celor n etape, fabrica a început să restituie împrumuturile astfel: primul împrumut a fost restituit, apoi conducerea fabricii a constatat că nu-și poate achita toate datoriile și a hotărât să restituie doar sume care nu au fost împrumutate în etape succesive. Să se determine care este suma totală maximă pe care o poate restitui fabrica.

Cerința

Cunoscând n – numărul de etape, ai – suma împrumutată în etapa i (1 ≤ i ≤ n), să se determine care este suma totală maximă pe care o poate restitui fabrica, știind că primul împrumut este întotdeauna achitat.

Date de intrare

Fișierul de intrare datorii.in conține pe prima linie n numărul de etape iar pe următoarea linie n valori naturale nenule a1, a2, …, an reprezentând sumele împrumutate în fiecare etapă.

Date de ieșire

Fișierul de ieșire datorii.out va conține pe prima linie un număr reprezentând suma totală maximă pe care o poate restitui fabrica.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ ai ≤ 10000

Exemplul 1:

datorii.in

6 
1 3 6 2 4 3 

datorii.out

11

Exemplul 2:

datorii.in

4
2 1 4 100

datorii.out

102