Subsequência Crescente Mais Longa 2

Dada uma lista (array) com n inteiros, é solicitado que se encontre a subsequência crescente mais longa dessa lista. Se existir mais de uma subsequência com o mesmo comprimento máximo, pode-se apresentar qualquer uma delas.

Uma subsequência de uma lista obtém-se removendo alguns (eventualmente nenhum) dos seus elementos, sem alterar a ordem dos restantes. Por exemplo, se a lista for , então é uma subsequência de . Já não é uma subsequência de , pois a ordem dos elementos não é mantida.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 100 000), o comprimento da lista.

A segunda linha contém n inteiros separados por espaços, (), que representam os elementos da lista.

Saída

O programa deve apresentar o comprimento da maior subsequência crescente da lista.

Exemplos

Explicação

1. No primeiro exemplo, a maior subsequência crescente da lista é .

2. No segundo exemplo, a maior subsequência crescente da lista é .