Fișierul intrare/ieșire	maxarea.in, maxarea.out	Sursă	Shumen Juniori 2015
Autor	Krassimir Manev	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	2 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Maxarea

E bine știut că este profitabil să construiești un hotel lângă mare. De aceea compania International Ocean Investment a cumpărat o bucată de pământ la coasta Marii Negre (similară cu cea din imagine) și i-ar plăcea să construiasă un hotel cât mai mare posibil. Din diverse motive, hotelul trebuie să aibă o bază dreptunghiulară. De aceea compania caută pe cineva care sa găsească suprafața dreptunghiulară de arie maximă care ar putea fi desenată pe bucata de pământ. Terenul a fost impărțit în N coloane de pătrățele egale (cele albe de pe figură). Coloanele sunt numerotate de la 1, 2, ..., N consecutiv, de la stânga la dreapta, iar dreptunghiul trebuie să fie compus dintr-un număr întreg de patrățele. Pentru fiecare coloană, numărul de pătrățele libere a fost numărat.

Cerință

Să se găsească suprafața dreptunghiulară de arie maximă care ar putea fi formată din patrățele.

Date de intrare

Fișierul de intrare maxarea.in va conține pe prima linie numărul întreg N. Pe următoarea linie se vor da N numere întregi D₁, D₂, ..., D_N – D_i reprezintă numărul de pătrățele de pe coloana i.

Date de ieșire

În fișierul de ieșire maxarea.out se va afișa aria maximă a unui dreptunghi care poate fi format din pătrățele.

Restricții

• N ≤ 1 000 000
• 0 < D_i ≤ 15 000

Exemplu