Se da un numar natural N
si un sir de N numere naturale
notate ai, i
= 0,N-1 cu proprietatea ca 0 <=
ai < N pentru orice i
= 0,N-1. Se numeste subpermutare a sirului dat orice multime {i1,
i2, ... im} care satisface urmatoarea proprietate:
Pentru orice i
din {i1, i2,
..., im} exista exact un j
din {i1, i2,
... im} pentru care aj
= i.
Spunem ca o subpermutare este mai mare decat o alta daca are cardinalul mai mare decat aceasta din urma.
Cerinta
Sa se determine cardinalul celei mai mari subpermutari a sirulul dat.
Date de intrare
Pe prima linie a fisierului de intrare subperm.in se
gaseste numarul natural N. Pe
urmatoarea linie se afla numerele a0,
a1, ... aN-1,
in aceasta ordine, separate prin spatii.
Date de iesire
Prima si singura linie a fisierului subperm.out va
contine cardinalul cerut.
Restrictii
10 000 <= N <= 500 000
Cardinalul unei permutari reprezinta numarul de elemente din permutare.
Exemplu
subperm.in
subperm.out
Explicatie
3
1 2 1
2
Multimea {1,
2} respecta proprietatea data
si este cea mai mare cu aceasta proprietate a1
= 2, a2 = 1.