Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 12 de abril
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #04]

[DAA 015] Rebentando os balões

Existem N balões a flutuar numa grande sala, alinhados da esquerda a para direita, cada um a uma altura H_i. A Maria gosta muito de arco e flecha e resolveu praticar um pouco. Ela dispara uma flecha da esquerda para a direita a uma altura arbitrária que ela própria escolhe.

A flecha move-se da esquerda a para direita a uma altura H até que encontra um balão nessa altura. No momento em que a flecha atinge um balão, rebenta-o, e a flecha continua o seu movimento da esquerda para a direita a uma altura que é decrementada em uma unidade. Dito de outro modo, se a flecha ia à altura H, depois de rebentar um balão passa a ir à altura H-1.

O Problema

Dado o número de balões e as suas alturas, a tua tarefa é calcular qual o menor número de flechas que a Maria precisa de disparar para rebentar todos os balões.

Input

A primeira linha de input contém um inteiro N, o número de balões.

A segunda linha contém N inteiros: as alturas H_i dos balões, da esquerda para a direita.

Output

Uma linha contendo um inteiro, que corresponde ao menor número de flechas a disparar para rebentar com todos os balões.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Input de Exemplo 1

5
2 1 5 4 3

Output de Exemplo 1

2

Explicação do Exemplo 1

É possível disparar uma flecha à altura 5, que rebenta os balões 5, 4 e 3, seguida de uma flecha à altura 2, que rebenta os balões 2 e 1.

Input de Exemplo 2

5
1 2 3 4 5	

Output de Exemplo 2

5

Input de Exemplo 3

5
4 5 2 1 4

Output de Exemplo 3

3

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto