Se dă un şir de N numere întregi A1, A2, ..., AN. 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 X = max { Ak | 1 ≤ k ≤ i },
Y = max { Ak | i+1 ≤ k ≤ j },
Z = max { Ak | j+1 ≤ k ≤ N }
şi suma S = X + Y + Z.
Cerinţă
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.
Date de intrare
Prima linie a fişierului de intrare secv.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 A1, A2, ..., AN separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire secv.out va conţine:
- 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.
Restricţii
• 3 ≤ N ≤ 30000
• A1, A2, ..., AN sunt numere întregi din intervalul [-10000, 10000]
• În cazul în care există mai multe soluţii se poate afişa oricare dintre ele.
Exemple
secv.in
secv.out
Explicaţii
7
3 2 1 5 6 3 2
10
2 3
Prima secvenţă : 3 2 – maximul este 3
A doua secvenţă : 1 – maximul este 1
A treia secvenţă : 5 6 3 2 – maximul este 6
Suma: 10