Area massima di un rettangolo in un istogramma
Dato un insieme di
n numeri che rappresentano le altezze delle barre in un istogramma, ti viene richiesto di calcolare l’area massima che è possibile ottenere senza uscire dai limiti delle barre.Tutte le barre dell’istogramma hanno una larghezza pari a 1, mentre le loro altezze sono interi non negativi di qualunque valore.
Input
La prima riga dell'input contiene un singolo intero
n (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da spazi (0 ≤ ≤ ).Output
Il programma deve stampare la massima area ottenibile dalle barre dell’istogramma.
Examples
Input | Output |
8
6 2 5 4 5 1 6 1 | 12 |
Hint
Per ogni barra nell'istogramma, si possono determinare due valori: l'elemento più vicino, a sinistra e a destra, che sia di altezza inferiore rispetto alla barra corrente. Questi valori sono sufficienti per calcolare l’area del rettangolo che ha come altezza proprio quella della barra in esame.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB