== include(page="template/taskheader" task_id="collar") ==

Poveste şi cerinţă...

Tassadar a descoperit un colier Xel’Naga format din $N$ perle, fiecare perlă $i$ având asociat un coeficient $V{~i~}$, iar frumuseţea colierului este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. Tassadar vrea să împartă colierul în mai multe coliere de lungimi egale, astfel încat fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial, fiecare perlă din colierul iniţial să facă parte din exact un colier nou, iar suma frumuseţilor colierelor noi să fie maximă.
 
Tassadar nu este un bijutier prea iscusit şi vă roagă pe voi să-i spuneţi care este suma frumuseţilor maximă pe care o poate obţine printr-o împărţire a colierului.

h2. Date de intrare

Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând frumuseţea fiecărei perle.

Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând coeficienţii perlelor.

h2. Date de ieşire

* $1 ≤ N ≤ 65.536$
* $-1.000.000.000 ≤ V{~i~} ≤ 1.000.000.000$

* colierul iniţial este circular

h2. Exemplu
table(example). |_. collar.in |_. collar.out |
| 6

1 4 2 3 1 2

4 2 3 1 2 1

| 5
|
h3. Explicaţie

Împărţim şirul în subsecvenţele $[1, 4, 2]$ şi $[3, 1, 2]$. O altă împărţire validă este $[1, 4]$ $[2, 3]$ $[1, 2]$.

Împărţim şirul în subsecvenţele $[1, 4, 2]$ şi $[3, 1, 2]$. O altă împărţire validă este $[1, 4]$ $[2, 3]$ $[1, 2]$ (putem considera aceste îmărţiri, deoarece colierul iniţial este circular).

== include(page="template/taskfooter" task_id="collar") ==