Plano de estacionamento

Tio Chico é o dono de um estacionamento para carros, localizado perto de um estádio de futebol. O estacionamento tem N vagas numeradas de 1 a N e em dias de jogo tem muita procura, podendo até mesmo lotar. Tio Chico é um tanto excêntrico, e decidiu que, no próximo jogo, deverá ser obedecida uma nova regra, que em termos gerais consiste no seguinte: o carro do i-ésimo cliente a chegar deverá ocupar uma vaga cujo número está dentro de um certo intervalo. Esses intervalos foram definidos pelo Tio Chico de acordo com alguns critérios, como espaços para manobra, sombreamento, etc. Mais especificamente, para o i-ésimo cliente que chegar, Tio Chico definiu um número V_i e determinou que o automóvel desse cliente deve ocupar uma vaga ainda não ocupada cujo número está dentro do intervalo 1,2,\ldots,V_i. Vamos chamar de plano de estacionamento a lista dos valores V_i, para todos os clientes i. Se um cliente chegar e não puder estacionar o carro de acordo com o plano de estacionamento, esse cliente não será atendido, e o estacionamento não aceitará o carro de nenhum outro cliente até o final do jogo. Você ficou muito preocupado com essa esquisitice to Tio Chico, e conhecendo o plano de estacionamento que foi definido, precisa determinar qual o maior número de clientes que poderão estacionar.

Entrada

Saída

Restrições

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000
• 1 ≤ V_i ≤ N, para 1 ≤ i ≤ N

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 40 pontos, N ≤ 2000 e M ≤ 2000.
• Para um conjunto de casos de testes valendo outros 60 pontos, nenhuma restrição adicional.

Exemplos

4
3
4
1
1

2
	

4
6
2
2
3
3
4
4

3