friends

Adisor si-a dat seama ca o parte dintre necazurile sale s-au datorat faptului ca nu si-a ales bine prietenii. Prin urmare, a luat o decizie importanta: va renunta la unii dintre ei.
Iata cum a procedat: mai întâi, a numerotat cei n prieteni de la 1 la n. Apoi a atasat fiecarui prieten i, câte un numar întreg C_i, denumit "calitate", care reprezinta în viziunea lui Adisor, suma algebrica a calitatilor si defectelor acelei persoane. Mai apoi a desenat un cerc, iar pe periferia acestuia a trecut în ordine valorile C₁, C₂,…C_n, astfel încât C_i se învecineaza cu C_i-1 si cu C_i+1, pentru oricare i cuprins între 2 si n-1. De asemenea, C₁ se învecineaza cu C_n si cu C₂, iar C_n se învecineaza cu C_n-1 si cu C₁.
În final, a stabilit criteriile dupa care-i va alege pe cei care-i vor ramâne si de acum înainte prieteni. Scopul sau este sa obtina o valoare maxima S, prin însumarea calitatilor individuale ale persoanelor pe care le selecteaza. Dispunerea pe cercul de prieteni, nu a fost facuta întâmplator: Adisor a asezat alaturi prieteni cu un comportament asemanator, astfel încât niciodata nu va alege doua persoane aflate pe pozitii consecutive pe cerc.
Ajutati-l pe Adisor sa-si selecteze viitorii prieteni, astfel încât sa fie respectate restrictiile de mai sus.

Cerinta

Scrieti un program care determina numarul natural S, reprezentând cea mai mare valoare care se poate obtine prin însumarea valorilor "calitatii" tuturor persoanelor care vor ramâne în continuare în relatii de prietenie cu Adisor.

Date de intrare

Fisierul friends.in contine pe prima linie numarul natural n reprezentand numarul de prieteni ai lui Adisor. Începând cu linia a doua, se gasesc n numere întregi C₁, C₂, … C_n, câte unul pe linie, reprezentând in ordine valorile "calitatii" fiecareia dintre persoane.

Date de iesire

Fisierul friends.out va contine o singura linie, pe care va fi afisat numarul natural S, cu semnificatia enuntata mai sus.

Restrictii

• 1 < n <= 25000
• -2000 <= C₁, C₂, ... C_n <= 2000
• Adisor are cel putin un prieten pentru care C_i>0.
  

Exemplu