Trova la più lunga sottosequenza crescente

Dato un array di n interi, devi trovare la più lunga sottosequenza crescente dell'array. Se ne esistono diverse con la stessa lunghezza, puoi restituirne una a tua scelta.

Una sottosequenza di un array si ottiene rimuovendo alcuni (eventualmente nessuno) elementi dall'array, senza alterare l'ordine di quelli rimanenti. Ad esempio, se l'array è , allora è una sottosequenza di , mentre non lo è, perché l’ordine degli elementi non è rispettato.

Input

La prima riga dell'input contiene un singolo intero n (1 ≤ n ≤ 100 000), che rappresenta la lunghezza dell'array.

La seconda riga contiene n numeri interi separati da spazi (), ovvero gli elementi dell'array.

Output

La prima riga deve contenere un intero k, che è la lunghezza della più lunga sottosequenza crescente dell'array.

La seconda riga deve contenere k interi separati da spazi, corrispondenti alla sottosequenza stessa. In caso di più soluzioni valide, puoi restituirne una qualsiasi.

Examples

Note

Nel secondo esempio, la sottosequenza è un’altra valida sottosequenza crescente di lunghezza 3.