Problem A
Pedreiro

Rubens é um jovem pedreiro, ele tem aprendido muitas técnicas novas com seu pai, que por sinal também é seu chefe. Juntos eles são donos de uma pequena empresa de construção e reforma. Como seu pai está ficando velho e este trabalho exige muito esforço físico, Rubens quer aprender todas as técnicas que seu pai sabe para que ele possa apenas comandar as obras.

Acontece que o pai de Rubens é um pedreiro muito experiente, e assim possui um conhecimento muito vasto no assunto, o que resulta no sucesso da empresa pois os clientes sempre ficam satisfeitos com o serviço e depois de algum tempo retornam para alguma reforma. Isso coloca uma pressão enorme sobre Rubens, pois ele deve sempre manter os padrões de seu pai.

Rubens está realizando a obra atual sem a presença de seu pai para mostrar que já é capaz de conduzir uma construção. Porém aconteceu um imprevisto, choveu na obra, e seu pai já ensinou que jamais se deve deixar uma poça d’água sobre os blocos da construção, mesmo que seja necessário quebrar alguns blocos para que a água possa escoar.

Como Rubens terá que reconstuir os blocos destruídos, ele deseja quebrar a menor quantidade possível de blocos. Além disso, se dois blocos estão na mesma coluna, Rubens só consegue remover o de baixo após quebrar o de cima.

O estado atual da obra pode ser modelado como $N$ colunas de blocos, e cada uma com uma altura $h_ i$. Dado o estado atual da obra, ajude Rubens calculando qual a menor quantidade de blocos que devem ser quebrados para que toda a água escoe.

A água flui sempre que não houver obstáculos (blocos acima do nível da água) à direita ou à esquerda, e se acumula quando há obstáculos em ambos os lados. Deve-se considerar que a chuva era uniforme em todas as colunas de blocos, e que choveu até que o estado das poças não mudasse mais. Por exemplo, considere o primeiro exemplo. Existem cinco colunas de blocos com as seguintes alturas: $5$, $2$, $3$, $4$, $5$. Depois de chover a altura dos poços de água sobre os blocos será: $0$, $3$, $2$, $1$, $0$, e para toda a água fluir, basta apenas quebrar os três primeiros blocos da primeira coluna.

Input

A primeira linha do input contém um inteiro $N$ ($1 \leq N \leq 10^6$), que indica a quantidade de colunas de blocos no estado atual da obra. A segunda linha do input contém $N$ inteiros $h_ i$ ($1 \leq h_ i \leq 10^6$) que representam a altura de cada coluna de blocos.

Output

Imprima uma linha contendo apenas um número inteiro, representando a quantidade mínima de blocos que devem ser quebrados para que toda água escoe da obra.

5
5 2 3 4 5

3

6
2 5 10 9 8 7

0

10
4 6 1 7 4 1 10 9 4 7

20