Seqüència creixent més llarga X57800

Sigui a = a₁, a₂, …, a_n una seqüència, diem que b = b₁, b₂, …, b_r = a_i1, a_i2, …, a_ir amb i_j < i_k si j < k i 1 ≤ i_j ≤ n és una subseqüència de a. Per exemple, si a = [1, 7, 9, 4, 8], b = [1, 7, 4] o b = [1,9,8] són subseqüències de a, però b = [2] o b = [7, 1] no ho són.

Sigui a = a₁, a₂, …, a_n una seqüència, diem que a és estrictament creixent si a_i < a_i+1 per tot i.

Donada una seqüència es demana trobar la subseqüència estrictament creixent més llarga. En cas que n’hi hagi més d’una, es demana la lexicogràficament menor.

Entrada

L’entrada consisteix en diversos casos, hi ha com a molt 200 casos. Cada cas consta de dues línies, la primera conté un enter 1 ≤ n ≤ 10⁵, la mida de la seqüència. La segona línia conté els n números de la seqüència, a_i amb 1 ≤ a_i ≤ 10⁹. La suma de la mida de totes les seqüències és menor que 5·10⁵.

Sortida

Escriviu la subseqüència estrictament creixent mé s llarga per a cada cas. Si n’hi ha mé s d’una escriviu la lexicogràficament menor.