Fişierul intrare/ieşire:	secv7.in, secv7.out	Sursă	ONI 2007, clasa 9
Autor	Adrian Diaconu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Secv7

Se da un sir de N numere intregi A₁, A₂, ..., 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 }
si suma S = X + Y + Z.

Cerinta

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.

Date de intrare

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₁, A₂, ..., A_N separate prin cate un spatiu.

Date de iesire

Fisierul de iesire secv7.out va contine:

• 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.

Restrictii

• 3 ≤ N ≤ 30000
• A₁, A₂, ..., A_N sunt numere intregi din intervalul [-10000,10000]
• In cazul in care exista mai multe solutii se poate afisa oricare dintre ele.

Exemplu

Explicatie

Prima secventa : 3 2 - maximul este 3
A doua secventa : 1 - maximul este 1
A treia secventa : 5 6 3 2 - maximul este 6
Suma: 10

Cum se trimit solutii?