Inima

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, \dots, 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ță

Cunoscând numărul $N$ de bătăi ale inimii unui pacient și intensitățile acestora $h_1, h_2, \dots, h_n$, determinați puterea maximă a inimii.

Date de intrare

Fișierul de intrare 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, \dots, h_n$, reprezentând intensitățile bătăilor inimii.

Date de ieșire

Fișierul de ieșire trebuie să conțină pe prima linie un număr natural $P$, unde $P$ este puterea maximă a inimii.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq h_i \leq 200$
• Pentru $50$ de puncte, $N \leq 1 \ 000$.

Exemplul 1

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$.

Exemplul 2

inima.in

2
1 1

inima.out

1

Explicație

Puterea maximă a inimii (partea colorată) între două bătăi este $1$.