Subsequência Crescente Mais Longa 1

Dado um array de n inteiros, o objetivo é encontrar a subsequência crescente mais longa desse array. Se houver várias subsequências com o mesmo comprimento, podes devolver qualquer uma delas.

Uma subsequência de um array obtém-se removendo alguns (possivelmente zero) elementos do array sem alterar a ordem dos elementos restantes. Por exemplo, se o array for , então é uma subsequência de , mas não é uma subsequência de , pois a ordem dos elementos não foi preservada.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 1000), que representa o comprimento do array.

A segunda linha contém n inteiros separados por espaços (), correspondendo aos elementos do array.

Saída

O programa deve imprimir o comprimento da subsequência crescente mais longa do array.

Exemplos

Explicação

1. No primeiro exemplo, a subsequência crescente mais longa do array é .

2. No segundo exemplo, a subsequência crescente mais longa do array é .