Plus longue sous-séquence croissante 1

On vous donne un tableau de n entiers, et l’objectif est de trouver la plus longue sous-séquence croissante de ce tableau. S’il en existe plusieurs, vous pouvez en renvoyer n’importe laquelle.

Une sous-séquence d’un tableau s’obtient en supprimant certains éléments (éventuellement aucun) sans changer l’ordre des éléments restants. Par exemple, si le tableau est a=[3,1,4,1,5,9,2,6,5]a = [3, 1, 4, 1, 5, 9, 2, 6, 5], alors [3,4,5,6][3, 4, 5, 6] est une sous-séquence de aa, tandis que [3,1,1,2,5][3, 1, 1, 2, 5] 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 entier n (1 ≤ n ≤ 1000), qui représente la taille du tableau.

La deuxième ligne contient n entiers séparés par des espaces a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \leq a_i \leq 10^9), 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

Entrée

Sortie

8
1 3 2 4 5 2 6 5

5

6
10 9 2 5 3 7

3

Explications

  1. Dans le premier exemple, la plus longue sous-séquence croissante de ce tableau est [1,2,4,5,6][1, 2, 4, 5, 6].

  2. Dans le deuxième exemple, la plus longue sous-séquence croissante de ce tableau est [2,5,7][2, 5, 7].

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB