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 $a = [3, 1, 4, 1, 5, 9, 2, 6, 5]$, então $[3, 4, 5, 6]$ é uma subsequência de $a$, mas $[3, 1, 1, 2, 5]$ não é uma subsequência de $a$, 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 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$), 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 é $[1, 2, 4, 5, 6]$.

2. No segundo exemplo, a subsequência crescente mais longa do array é $[2, 5, 7]$.