Máximo de Islas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Siempre que llueve el campo del Bitman termina inundado. Sin embargo, como el campo no está perfectamente nivelado, se llena de agua de una manera no uniforme, y quedan un número de "islas" separadas por extensiones de agua. El campo de Bitman se describe como un paisaje de una sola dimensión especificado por N (1 \le  N \le  100,000) valores consecutivos de alturas H_1...H_n. Asumiendo que el paisaje está rodeado por muros altos de altura prácticamente infinita, considere qué pasa durante una tormenta: las regiones son cubiertas primero por agua, y se forma un conjunto de "islas" disjuntas, las cuales serán cubiertas todas por agua si el agua continúa elevándose. En el instante en que el nivel del agua sea igual a la altura de un pedazo de tierra, ese pedazo de tierra se considera que está bajo agua.

Descripcion

Se muestra un ejemplo de arriba a la izquierda en el que hemos añadido únicamente 1 unidad de agua, lo que deja 4 islas (el máximo que se verá). Más tarde, después de añadir un total de 7 unidades de agua, llegamos a la figura de la derecha con solamente dos islas expuestas. Por favor, calcule el número máximo de islas que veremos en algún momento durante la tormenta hasta que el campo quede totalmente cubierto por agua.

Entrada

La entrada contiene:

  • Línea 1: El entero N.
  • Líneas 2.. N+1: La línea i+1 contiene la altura H_i (1 \le H_i \le 1,000,000,000)

Salida

En una sola línea escribir un solo entero, el número máximo de islas que aparecen en cualquier momento en el transcurso de una tormenta.

Ejemplo de Entrada

8          
3 
5 
2 
3 
1 
4 
2 
3

Ejemplo de Salida

4

El ejemplo coincide con la figura mostrada.


Comments

There are no comments at the moment.