Mircea Măierean (mirceamaierean) Medicii de la Institutul Inimii doresc să calculeze puterea maximă a inimii unui pacient, utilizând măsurători făcute cu aparate electronice.
Se dau n numere naturale, reprezentând intensitățile bătăilor unei inimi la intervale de o secundă. Intensitățile pot fi vizualizate ca n linii verticale de înălțimi \({h}_{1}, {h}_{2}, … {h}_{n}\). Distanța dintre două linii consecutive este 1.
Puterea maximă a unei inimi se definește ca fiind aria maximă a unui dreptunghi care se poate obține între două bătăi oarecare ale inimii.
Cerința
Cunoscând numărul n de bătăi ale inimii unui pacient și intensitățile acestora \({h}_{1}, {h}_{2}, … {h}_{n}\), determinați puterea maximă a inimii.
Date de intrare
Fișierul de intrare inima.in conține pe prima linie un număr natural N reprezentând numărul de bătăi ale inimii. Pe linia a doua se găsesc n numere naturale separate prin câte un spațiu: \({h}_{1}, {h}_{2}, … {h}_{n}\), reprezentând intensitățile bătăilor inimii.
Date de ieșire
Fișierul de ieșire inima.out va conține pe prima linie un număr natural p, unde p este puterea maximă a inimii.
Restricții și precizări
1 ≤ n ≤ 100 000- \(1 ≤ {h}_{i} ≤ 200\)
- Pentru 50 de puncte,
n ≤ 1000
Exemplu:
inima.in
9 1 8 6 2 5 4 8 3 7
inima.out
49
Explicație
Puterea maximă a inimii (partea colorată) între două bătăi este 49
inima.in
2 1 1
inima.out
1
Explicație
Puterea maximă a inimii (partea colorată) între două bătăi este 1
