datorii

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ţă

Cunoscând $n$-numărul de etape, ai suma împrumutată în etapa $i$, 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 $a_1, a_2, \dots a_n$ 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 \leq n \leq 1 \ 000$
• $1 \leq a_i \leq 10 \ 000$

Exemplul 1

datorii.in

6
1 3 6 2 4 3

datorii.out

11

Exemplul 2

datorii.in

4
2 3 4 100

datorii.out

102