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

Fie un şir $a{~1~}$, $a{~2~}$, ..., $a{~N~}$ 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 $a{~1~}$, $a{~2~}$, ..., $a{~i~}$, a doua din elementele $a~i+1~$, $a~i+2~$, ..., $a~j~$, a treia din elementele $a~j+1~$, $a~j+2~$, ..., $a~k~$ şi ultima din elementele $a~k+1~$, $a~k+2~$, ..., $a~n~$. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

Fie un şir $a{~1~}$, $a{~2~}$, ..., $a{~N~}$ 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 $a{~1~}$, $a{~2~}$, ..., $a{~i~}$, a doua din elementele $a{~i+1~}$, $a{~i+2~}$, ..., $a{~j~}$, a treia din elementele $a{~j+1~}$, $a{~j+2~}$, ..., $a{~k~}$ şi ultima din elementele $a{~k+1~}$, $a{~k+2~}$, ..., $a{~n~}$. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

h2. Cerinţă

h2. Restricţii
* $8 ≤ N ≤ 5 000$

* $0 ≤ ai ≤ 100 000 000$, pentru orice $i = 1..N$

* $0 ≤ a{~i~} ≤ 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.

8925