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 Ci,
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 C1,
C2,…Cn,
astfel încât Ci se învecineaza cu Ci-1
si cu Ci+1, pentru
oricare i cuprins între 2 si n-1.
De asemenea, C1 se
învecineaza cu Cn
si cu C2, iar Cn se învecineaza cu Cn-1
si cu C1.
Î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 friends2.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
C1, C2, … Cn,
câte unul pe linie, reprezentând in ordine valorile "calitatii"
fiecareia dintre persoane.
Date de iesire
Fisierul friends2.out
va contine o singura linie, pe care va fi afisat numarul natural S,
cu semnificatia enuntata mai sus.
Restrictii
1 < n <= 25000
-2000 <= C1, C2,
... Cn <= 2000
Adisor are cel putin un prieten pentru care Ci>0.
Exemplu
friends2.in
friends2.out
Explicatie
5
7
3
-2
1
6
9
Adisor îl selecteaza
pe al doilea prieten, cu "calitatea" 3
si pe al cincilea, cu "calitatea" 6.