Plus longue sous-séquence croissante 2

Étant donné un tableau de n entiers, vous devez déterminer la plus longue sous-séquence croissante de ce tableau. S’il existe plusieurs sous-séquences de longueur maximale, vous pouvez en retourner n’importe laquelle.

Une sous-séquence d’un tableau s’obtient en supprimant certains (éventuellement aucun) éléments du tableau, tout en conservant l’ordre des éléments restants. Par exemple, si le tableau est , alors est une sous-séquence de . En revanche, n’en est pas une, car l’ordre des éléments n’est pas respecté.

Entrée

La première ligne de l’entrée contient un seul entier n (1 ≤ n ≤ 100 000), la taille du tableau.

La deuxième ligne contient n entiers séparés par des espaces (), qui représentent les éléments du tableau.

Sortie

Le programme doit afficher la longueur de la plus longue sous-séquence croissante du tableau.

Exemples

Explication

1. Dans le premier exemple, la plus longue sous-séquence croissante du tableau est .

2. Dans le deuxième exemple, la plus longue sous-séquence croissante du tableau est .