Cerința

Suntem în anul 2050. Resursele de apă de pe planeta noastră sunt limitate din cauza schimbărilor climatice. Sistemul de stocare a apei al unui oraș a evoluat în timp, ajungându-se la o configurație flexibilă formată din n pereţi verticali paraleli \( {p}_{1}, {p}_{2}, \cdots {p}_{n} \). Fiecare perete \( {p}_{i} \) are forma unui dreptunghi cu înălțimea \( {a}_{i} \) şi lăţimea de 1 km, iar oricare doi pereţi alăturaţi \( {p}_{i}, {p}_{i+1} \) se află la distanţa de 1 km, faţă în faţă. Fiecare dintre acești pereți poate fi coborât complet, prin culisare pe verticală, iar un bazin poate fi format din oricare doi pereți \( {p}_{i}, {p}_{j} \) (rămaşi după coborârea tuturor celorlalți) şi din pereţi laterali, care întregesc conturul de bazin. Capacitatea unui bazin este dată de produsul dintre înălţimea peretelui celui mai mic dintre cei doi \( {p}_{i}, {p}_{j} \) din care este format bazinul şi distanța dintre aceşti doi pereți. Sistemul de stocare poate fi descris de un șir de numere naturale \( {a}_{1}, {a}_{2}, …..{a}_{n} \)strict pozitive, unde \({a}_{1} \)reprezintă înălțimea în kilometri a peretelui \({p}_{1} \), \({a}_{2} \) reprezintă înălțimea în kilometri a peretelui \({p}_{2} \) și așa mai departe.

Scrieți un program care primește la intrare numărul de pereți n≥2 și înălțimile acestora \( {a}_{1}, {a}_{2}, \cdots {a}_{n} \) , iar apoi determină și scrie capacitatea maximă de apă care poate fi stocată în acel oraș.

Date de intrare

Fișierul de intrare fmi_orase1.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire fmi_orase1.out va conține pe prima linie numărul rez, reprezentând capacitatea maximă de apă care poate fi stocată în acel oraș.

Restricții și precizări

• 2 ≤ n ≤ 100
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 100

Exemplu:

fmi_orase1.in

9
1 8 6 2 5 4 8 3 7

fmi_orase1.out

49

Explicație

Peretele al doilea de înălțime 8 km și cel de-al nouălea de înălțime 7 km rămân ridicați (toți ceilalți fiind coborâți), ei determinând astfel bazinul de capacitate maximă care poate reține 49 \( {km}^{3} \) de apă..