Sottosequenza Crescente Più Lunga 1

Dato un array di n interi, ti viene richiesto di trovare la sottosequenza crescente più lunga dell’array. Nel caso in cui ne esistano più di una, puoi restituirne una qualsiasi.

Una sottosequenza di un array si ottiene eliminando alcuni (eventualmente zero) elementi dall’array, senza modificare l’ordine di quelli rimanenti. Ad esempio, se l'array è , allora è una sottosequenza di , mentre non è una sottosequenza di , poiché non viene preservato l’ordine degli elementi.

Input

La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 1000), la lunghezza dell’array.

La seconda riga contiene n interi separati da uno spazio (), che rappresentano gli elementi dell’array.

Output

Il programma deve stampare la lunghezza della sottosequenza crescente più lunga dell’array.

Esempi

Spiegazione

1. Nel primo esempio, la sottosequenza crescente più lunga dell’array è .

2. Nel secondo esempio, la sottosequenza crescente più lunga dell’array è .