Pracsiu Dan (dnprx) 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 ≤ 10001 ≤ 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