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 possuir á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 $H_i$, 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 \leq N \leq 10^5, 1 \leq H_i \leq 10^9 \; \; (1 \leq i \leq N)$

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a $20$ pontos, $N \leq 10^3$.

Exemplos

Exemplo de entrada 1

4
2
1
1
2

Exemplo de saída 1

2

Exemplo de entrada 2

6
5
2
6
1
3
2

Exemplo de saída 2

2

Exemplo de entrada 3

17
4
3
2
1
1
1
1
1
2
3
5
5
3
3
2
4
4

Exemplo de saída 3

12