Selecție CPPI 2024 - Mirror Juniori | Splitmax

Cerință

Avem un șir de numere naturale așezate pe poziții de la $1$ la $n$. Se cere să determinăm o poziție $p$ ($1 \leq p \lt n$) cu proprietatea că suma elementelor din șir de poziții de la $1$ la $p$ (inclusiv) înmulțită cu suma elementelor din șir de pe poziții de la $p+1$ la $n$ (inclusiv) este maximă. Dacă sunt mai multe variante de alegere a poziției $p$, se cere soluția cu $p$ minim.

Date de intrare

Fișierul splitmax.in conține pe prima linie valoarea $n$ iar pe linia a 2-a, elementele șirului dat, separate prin spațiu.

Date de ieșire

Fișierul splitmax.out conține un întreg ce reprezintă valoarea $p$ determinată conform cerinței.

Restricții și precizări

• $2 \leq n \leq 100 \ 000$;
• Valorile din șir sunt numere naturale nenule cu cel mult $9$ cifre.

Exemplu

splitmax.in

3
6 3 4

splitmax.out

1

Explicație

Produsul maxim care se poate obține este $6 \cdot (3+4)$.