Problema C - Contrabando de Mel

O Darth Vader, como indivíduo extremamente culto, tem uma grande estima pela IOI (International Olympiad in Informatics) e por isso não podia deixar de estar presente na 25ª edição da competição, na Austrália. Antes de apanhar uma nave de transporte intraterráqueo, ficou alojado uma noite num hotel. No dia de partida, não pôde deixar de comer um bom pequeno-almoço. Foi aí que visionou uma pequena maravilha da natureza: um mini-pote de mel.

Sem ninguém notar, o Darth Vader colocou um largo conjunto de mini-potes de mel de baixo da capa e foi para o espaçoporto. Infelizmente aí deparou-se com um problema: como passar os mini-potes de mel pela segurança?

O Darth Vader tem à sua disposição N malas de viagem seguidas, numa linha (a ordem é mantida sempre). Cada mala pode levar no máximo um único mini-pote de mel. No entanto, se existirem mini-potes mel muito próximos uns dos outros a segurança pode desconfiar que o Darth Vader está a fazer contrabando e prendê-lo. Cada mala tem um alcance pré-determinado A_i. O alcance de cada mala representa a distância mínima a que tem de estar a próxima mala (à frente ou atrás) com um mini-pote de mel (a distância mede-se em número de malas no intervalo).

Como exemplo, imagina que o Darth Vader tem um conjunto de malas com os seguintes alcances:

3 3 2 1 3 2

Se pusermos um mini-pote na terceira mala (que tem alcance 2) só podemos pôr mini-potes na primeira mala e a partir da quinta mala (de alcance 3).

Com estas condicionantes, qual o número máximo de potes de mel que é possível colocar?

O Problema

Dado um conjunto de N malas e os respetivos alcances A_i, a tua tarefa é determinar o número máximo de mini-potes de mel que o Darth Vader consegue levar para a Austrália sem ser preso por contrabando. Podes assumir que o número de mini-potes de mel disponíveis era suficiente para encher todas as malas, se tal fosse possível.

Input

Na primeira linha vem um único número inteiro N, indicando o número de malas.

Segue-se uma linha com N números inteiros (separados por um único espaço) onde o i-ésimo número representa o alcance A_i da i-ésima mala.

Output

Uma linha contendo um único inteiro que representa o maior número de mini-potes de mel que o Darth Vader pode levar.

Restrições

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

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 30% dos pontos, o valor de N será menor ou igual a 20.

Para um conjunto de casos de teste valendo 60% dos pontos, o valor de N será menor ou igual a 100.

Exemplo de Input 1

5
1 2 3 2 1

Exemplo de Output 1

2

Clarificação de Output 1

A resposta corresponde à seguinte situação (existem várias possíveis):

X - - - X

Onde o 'X' representa uma mala escolhida e '-' uma não escolhida.

Exemplo de Input 2

7
1 7 2 7 2 3 1

Exemplo de Output 2

4