Encontre a Subsequência Crescente Mais Longa

Dado um array de n inteiros, pretende-se encontrar a subsequência crescente mais longa desse array. Se existirem várias subsequências possíveis com esse comprimento, pode apresentar qualquer uma delas.

Uma subsequência de um array é obtida ao remover alguns (possivelmente nenhum) elementos do array, sem alterar a ordem dos que restam. 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 é preservada.

Entrada

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

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

Saída

A primeira linha deve conter um único inteiro k - o comprimento da subsequência crescente mais longa do array.

A segunda linha deve conter k inteiros separados por espaço, que representem a subsequência mais longa. Se existirem várias respostas possíveis, pode apresentar qualquer uma delas.

Exemplos

Nota

No segundo exemplo, a subsequência também é uma subsequência crescente válida de comprimento 3.