Splitmax3

Cerință

Se dă un șir de n numere naturale. Să se determine două poziții $i$ și $j$ cu proprietatea că suma elementelor aflate pe poziții de la $1$ la $i$ (inclusiv) înmulțită cu suma elementelor aflate pe poziții de la $i+1$ la $j$ (inclusiv) și înmulțită cu suma elementelor aflate pe poziții de la $j+1$ la $n$ (inclusiv) este maximă.

Date de intrare

Fișierul splitmax3.in conține pe prima linie numărul $n$. Pe linia a doua se află n numere naturale separate prin spațiu.

Date de ieșire

Fișierul splitmax.out conține pe prima linie trei numere, separate prin spațiu: $M$, $i$, $j$ reprezentând respectiv valoarea maximă obținută respectiv pozițiile $i$ și $j$ conform cerinței. Dacă sunt mai multe soluții cu $M$ maxim, o alegem pe cea cu $i$ minim.

Restricții și precizări

• $3 \leq n \leq 100 \ 000$;
• $1 \leq i \lt j \leq n$;
• Valorile șirului sunt naturale nenule de o cifră.
• Valoarea cerută are maxim $18$ cifre.

Exemplu

splitmax3.in

5
1 3 1 4 7

splitmax3.out

140 2 4