Problema La colindat

Alina și Daniel merg la colindat! Momentan, aceștia se află pe o stradă mai ciudată, unde cele n case sunt așezate doar pe o parte. Ei încep cu prima casă și continuă până la ultima casă de pe stradă. Amândoi știu doar o singură colindă de Crăciun, prin urmare, dacă colindă o casă, nu pot colinda casa următoare, pentru ca vecinii din casa următoare să nu își dea seama că au colindat același lucru. Se știe pentru fiecare casă câte portocale ar primi amândoi dacă ar colinda-o.

Cerință

Să se determine numărul maxim de portocale pe care îl pot obține cei doi dacă aleg optim o serie de case de colindat, fără ca două dintre case să fie consecutive pe stradă.

Date de intrare

Programul citește de la tastatură, de pe prima linie, numărul natural n, reprezentând numărul de case de pe stradă, iar de pe următoarea linie, n numere naturale, al i-lea număr reprezentând numărul de portocale pe care le-ar obține Alina și Daniel dacă ar colinda casa i (1 ≤ i ≤ n).

Date de ieșire

Programul afișează pe ecran numărul maxim de portocale pe care le-ar putea obține Alina și Daniel dacă aleg în mod optim o serie de case de colindat (fără ca două dintre casele colindate să fie consecutive pe stradă).

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ numărul de portocale oferite de case ≤ 1000

Exemplu