XXVI Olimpíada Brasileira de Informática
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 |
