Recollint aigua de pluja P17735

Una elevació de terreny d’altura $h$ en un punt concret es pot representar mitjançant una barra vertical formada per $h$ quadrats de mida $1\times 1$. En conseqüència, una seqüència d’$n$ enters representa un mapa 2D d’elevació de terreny en $n$ punts contigus, formant una projecció vertical del perfil del terreny.

Quan plou, es recull l’aigua de la pluja a les àrees de terreny que queden ensotades entre altres més altes. Per exemple, aquest és el volum màxim d’aigua que es podria recollir després d’una tempesta per a la seqüència { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }:

Donada una seqüència d’enters que representa un mapa 2D d’elevació de terreny, dibuixeu l’aigua recollida després d’una bona tempesta.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 3 i $10^5$, seguida de les $n$ elevacions, totes nombres naturals.

Sortida

Per a cada cas, dibuixeu el terreny després d’una tempesta. Marqueu el terreny amb ‘X’, l’aigua amb punts, i encercleu tot el dibuix amb guions i barres verticals com es pot veure als exemples.