== include(page="template/taskheader" task_id="clasa1") ==
$Ați fost șmecheri, ați făcut problema clasa0? Vă provoc să faceți și problema clasa1!$
Din nou este vorba de doamna învățătoare Cristina, care de data asta vrea să își grupeze elevii în grupe formate de copii consecutivi în șirul inițial. Din nou doamna învățătoare vrea să facă grupe după colegiabilitatea elevilor, fiecărui elev i se va atrebui o valoare care este gradul de colegiabilitate. Gradul de sociabilitate al unui grup este diferența maximă dintre nivelul de colegiabilitate a doi elevi. Dacă în grup este doar un elev gradul de sociabilitate al acelui grup este 0.
Din nou este vorba de doamna învățătoare Cristina, care de data aceasta vrea să împartă elevii în grupe formate din copii consecutivi în șirul inițial. Din nou doamna învățătoare vrea să formeze grupe după colegialitatea elevilor. Gradul de socializare al unui grup este diferența maximă dintre nivelul de colegialitate a doi elevi. Dacă o grupă are doar un elev gradul de socializare al acelei grupe este 0.
h2. Cerință
Doamna învățătoare vrea să știe care este suma maximă a gradelor de sociabilitate a grupurilor. Voi trebuie să o ajutați!
Doamna învățătoare vrea să știe care este suma maximă a gradelor de socializare a grupelor. Voi trebuie să o ajutați!
h2. Date de intrare
Fișierul de intrare $clasa1.in$ pe prima linie *n*, numărul de elevi din clasa doamnei Cristina. Pe cea de a doua linie vom avea c[~1~], c[~2~], ..., c[~n~], însemnând gradul de colegiabilitate al fiecăruia.
Fișierul de intrare $clasa1.in$ va conține pe prima linie *n*, numărul de elevi din clasa doamnei Cristina. Pe cea de a doua linie vom avea *c[~1~]*, *c[~2~]*, ..., *c[~n~]*, nivelul de colegialitate al fiecăruia.
h2. Date de ieșire
În fișierul de ieșire $clasa1.out$ trebuie să se afle valoarea dorită de doamna profesoară.
În fișierul de ieșire $clasa1.out$ se va afla valoarea dorită de doamna învățătoare.
h2. Restricții
* $1 ≤ *n* ≤ 1000000$
* $-10[^9^] ≤ *c[~i~]* ≤ 10[^9^]$
* $1 ≤ *c[~i~]* ≤ 10[^9^]$
h2. Exemplu
table(example).
|_. clasa1.in |_. clasa1.out |_. Explicație |
| 5
1 2 3 1 2
1 2 3 1 2
| 3
| Prima grupă este formată din elevii de pe pozițiile 1, 3 și 5, iar a doua grupă din elevii de pe pozițiile 2 și 4.
| O soluție posibilă este (1 2 3) (1 2).
O altă soluție posibilă este (1 2) (3 1) (2).
|
