Submeta sua solução

Arquivo:

Linguagem: Selecione C++17 / g++ C17 / gcc Javascript Java / JDK Python 3 / CPython

Submete

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 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 ≤ N ≤ 10⁵, 1 ≤ H_i ≤ 10⁹ \; \; (1 ≤ i ≤ N)

Informações sobre a pontuação

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

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