secv

Se dă un şir de $N$ numere întregi $A_1, A_2, \ldots , 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:

• $X = max \{ A_k | \ 1 \leq k \leq i \}$
• $Y = max \{ A_k | \ i+1 \leq k \leq j \}$
• $Z = max \{ A_k | \ j+1 \leq k \leq N \}$
• 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 $A_1, A_2, \ldots, A_N$ 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 și precizări

• $3 \leq N \leq 30 \ 000$
• $A_1, A_2, \ldots , A_N$ sunt numere întregi din intervalul $[-10 \ 000, 10 \ 000]$
• În cazul în care există mai multe soluţii se poate afişa oricare dintre ele

Exemplu

secv.in

7
3 2 1 5 6 3 2

secv.out

10
2 3

Explicație

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$