== include(page="template/taskheader" task_id="secv7") ==
Se dă un şir de $N$ numere întregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$}. Asupra acestui şir se poate efectua următoarea operaţie: se împarte şirul în $3$ secvenţe nevide, se calculează valoarea maximă din fiecare secvenţă şi apoi se face suma acestor valori. Cu alte cuvinte se aleg doi indici $0 < i < j < N$ şi se calculează valorile
Se da un sir de $N$ numere intregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$}. Asupra acestui sir se poate efectua urmatoarea operatie: se imparte sirul in $3$ secvente nevide, se calculeaza valoarea maxima din fiecare secventa si apoi se face suma acestor valori. Cu alte cuvinte se aleg doi indici $0 < i < j < N$ si se calculeaza valorile
{$X = max { A{~k~} | 1 ≤ k ≤ i }$},
{$Y = max { A{~k~} | i+1 ≤ k ≤ j }$},
{$Z = max { A{~k~} | j+1 ≤ k ≤ N }$}
ÅŸi suma {$S = X + Y + Z$}.
si suma {$S = X + Y + Z$}.
h2. Cerinţă
h2. Cerinta
Calculaţi valoarea minimă a lui $S$ care se poate obţine în urma unei astfel de operaţii şi determinaţi cei doi indici care separă secvenţele pentru a obţine această valoare.
Calculati valoarea minima a lui $S$ care se poate obtine in urma unei astfel de operatii si determinati cei doi indici care separa secventele pentru a obtine aceasta valoare.
h2. Date de intrare
Prima linie a fişierului de intrare $secv7.in$ conţine un număr natural $N$ reprezentând numărul de elemente al şirului de intrare, iar a doua linie conţine numerele întregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} separate prin câte un spaţiu.
Prima linie a fisierului de intrare $secv7.in$ contine un numar natural $N$ reprezentand numarul de elemente al sirului de intrare, iar a doua linie contine numerele intregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} separate prin cate un spatiu.
h2. Date de iesire
Fişierul de ieşire secv7.out va conţine:
Fisierul de iesire $secv7.out$ va contine:
* pe prima linie: valoarea minimă a sumei;
* pe a doua linie: două numere naturale $i,j$ separate printr-un spaţiu, reprezentând indicii pentru care se obţine valoarea minimă pentru $S$ prin aplicarea operaţiei descrise mai sus.
* pe prima linie: valoarea minima a sumei;
* pe a doua linie: doua numere naturale $i,j$ separate printr-un spatiu, reprezentand indicii pentru care se obtine valoarea minima pentru $S$ prin aplicarea operatiei descrise mai sus.
h2. Restrictii
* $3 ≤ N ≤ 30000$
* {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} sunt numere întregi din intervalul [{$-10000,10000$}]
* În cazul în care există mai multe soluţii se poate afişa oricare dintre ele.
* {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} sunt numere intregi din intervalul [{$-10000,10000$}]
* In cazul in care exista mai multe solutii se poate afisa oricare dintre ele.
h2. Exemplu
