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

Fie un şir a1, a2, ..., aN de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element

Fie un şir $a1$, $a2$, ..., $aN$ de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element

din şir să aparţină unei singure secvenţe şi fiecare secvenţă să conţină cel puţin două elemente. Mai exact, se

identifică trei indici i < j < k astfel încât prima secvenţă este formată din elementele a1, a2, ..., ai,
a doua din elementele ai+1, ai+2, ..., aj, a treia din elementele aj+1, aj+2, ..., ak şi ultima din
elementele ak+1, ak+2, ..., an. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre

identifică trei indici $i$ < $j$ < $k$ astfel încât prima secvenţă este formată din elementele $a1$, $a2$, ..., $ai$,
a doua din elementele $ai+1$, $ai+2$, ..., $aj$, a treia din elementele $aj+1$, $aj+2$, ..., $ak$ şi ultima din
elementele $ak+1$, $ak+2$, ..., $an$. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre

valoarea maximă şi cea minimă din acea secvenţă.
h2. Cerinţă

h2. Date de intrare

Fişierul de intrare $split.in$ conţine pe prima linie numărul natural N. Pe linia a doua se găsesc N numere naturale,
separate prin câte un spaţiu, reprezentând elementele şirului a.

Fişierul de intrare $split.in$ conţine pe prima linie numărul natural $N$. Pe linia a doua se găsesc $N$ numere naturale,
separate prin câte un spaţiu, reprezentând elementele şirului $a$.

h2. Date de ieşire
În fişierul de ieşire $split.out$ conţine pe prima linie un singur număr natural reprezentând suma maximă a costurilor

celor patru secvenţe. Pe linia a doua se află trei numere naturale i, j şi k, separate prin câte un spaţiu, cu

celor patru secvenţe. Pe linia a doua se află trei numere naturale $i$, $j$ şi $k$, separate prin câte un spaţiu, cu

semnificaţia din enunţ.
h2. Restricţii

8 ≤ N ≤ 5 000
0 ≤ ai ≤ 100 000 000, pentru orice i = 1..N
O secvenţă poate avea costul 0 (valoarea maximă egală cu valoarea minimă)
Dacă există mai multe soluţii cu aceeaşi sumă maximă, atunci se va alege soluţia cu i minim. Dacă
există mai multe soluţii cu acelaşi i minim, se alege aceea cu j minim, iar dacă există mai multe soluţii
cu acelaşi i şi j minim, se alege aceea cu k minim.

* $8 ≤ N ≤ 5 000$
* $0 ≤ ai ≤ 100 000 000$, pentru orice $i = 1..N$
* O secvenţă poate avea costul $0$ (valoarea maximă egală cu valoarea minimă)
* Dacă există mai multe soluţii cu aceeaşi sumă maximă, atunci se va alege soluţia cu $i$ minim. Dacă
există mai multe soluţii cu acelaşi $i$ minim, se alege aceea cu $j$ minim, iar dacă există mai multe soluţii
cu acelaşi $i$ şi $j$ minim, se alege aceea cu $k$ minim.

h2. Exemplu

h3. Explicaţie

Cele 4 secvenţe sunt:
9 7 3 0 (cost 9 – 0 = 9)
2 1 8 (cost 8 – 1 = 7)
6 0 (cost 6 – 0 = 6)
11 4 (cost 11 – 4 = 7)
O altă soluţie care obţine tot suma maximă 29 este
5 7 9, dar nu are i minim.

Cele $4$ secvenţe sunt:
$9 7 3 0$ (cost $9 – 0 = 9$)
$2 1 8$ (cost $8 – 1 = 7$)
$6 0$ (cost $6 – 0 = 6$)
$11 4$ (cost $11 – 4 = 7$)
O altă soluţie care obţine tot suma maximă $29$ este
$5 7 9$, dar nu are $i$ minim.

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