Paravent – Regional event 2016

Level 2

Énoncé

Pas de répit pour les Prolosaures ! La mer étant à peine redescendue à son niveau normal, une nouvelle prophétie annonce la venue d'un ouragan.

Des vents violents venus de l'ouest emporteront tout ce qui sera exposé, mais ils seront interceptés par le relief montagneux, derrière lequel les Prolosaures seront à l'abri de la catastrophe imminente.

Votre but est de déterminer la surface totale protégée par les montagnes.

Entrée

  • La première ligne est un entier n, la largeur du continent.
  • La ligne suivante contient n entiers h1, …, hn séparés par des espaces donnant les altitudes du terrain, d'ouest en est.

Le vent arrive de la gauche (de l'ouest) et lorsqu'il rencontre une montagne, toutes les terres qui sont plus à droite et de hauteurs inférieures à celle-ci sont à l'abri.

Chaque altitude correspond à un terrain d'une unité de surface.

Sortie

La sortie est un unique entier qui est la surface d'abri disponible.

Contraintes

  • 1 ≤ n ≤ 100 000
  • 0 ≤ h ≤ 100 000

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
10
30 27 17 42 29 12 14 41 42 42
Sample output
6
Note

Tout ce qui est dans la zone rouge sera emporté par la tempête.

Submit your solution

You have to register or log in to be able to submit your solution.