Fie un vector cu n elemente numere naturale.

Cerința

Determinați suma maximă care se poate obține prin adunarea valorilor care nu se află pe poziții consecutive în vector.

Date de intrare

Fișierul de intrare smax.in conține pe prima linie numărul n, care reprezintă numărul de valori din vector. Pe a doua linie a fișierului se află cele n elemente ale vectorului.

Date de ieșire

Fișierul de ieșire smax.out va conține pe prima linie numărul S, reprezentând suma maximă care se poate obține din adunarea valorilor care nu se află pe poziții consecutive.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplu:

smax.in

4
1 4 5 4

smax.out

8

Explicație

Suma maximă este 8 și se obține din valorile aflate pe pozițiile 2 și 4.