XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: chuva.x, onde x deve ser c, cpp, java, js ou py

Chuva

É período de chuva no Reino Quadrado. Nos últimos anos, o Rei Maior Quadrado (RMQ) ordenou a construção de uma enorme piscina para refrescar seus súditos. A piscina é composta por diversas seções de mesma largura e comprimento, mas podem ter alturas diferentes. A altura de cada seção é um número inteiro em metros. Durante o período de chuvas fortes, o Rei nem precisa gastar água para encher a piscina - basta deixar que a chuva faça esse trabalho. A chuva cai uniformemente em todas as seções da piscina, enchendo - até que não haja mais capacidade para acumular água. O Rei o contratou para calcular quantas seções estarão cobertas com água, durante a estação de chuva. Uma seção da piscina pode ser considerada coberta com água se ela possuír água com pelo menos 1m de profundidade. O caso do exemplo 3 pode ser visto na figura abaixo, que apresenta um corte lateral da piscina. As seções 2 a 10 e 13 a 15 ficarão cobertas de água.

Entrada

A primeira linha contém um inteiro, N, o número de seções da piscina. Seguem N linhas, cada uma com um inteiro Hi, a altura da i-ésima seção, em metros.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o número de seções da piscina cobertos por água.

Restrições

  • 1 ≤ N ≤ 105, 1 ≤ Hi ≤ 109 \; \; (1 ≤ i ≤ N)

Informações sobre a pontuação

  • Em um conjunto de casos de teste equivalente a 20 pontos, N ≤ 103.

Exemplos

Entrada
4
2 
1 
1 
2
Saída
2
	

 

Entrada
6
5 
2 
6 
1 
3
Saída
2
	

 

Entrada
17
4
3
2
1
1
1
1
1
2
3
5
5
3
3
2
4
4
Saída
12
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação