Se citesc n perechi de numere (a,b), cu a<b pentru fiecare pereche. O pereche (c,d) poate urma dupa perechea (a,b) intr-un lant daca b<c. Determinati, folosind Programarea Dinamica, lungimea maxima a unui lant de perechi ce se poate forma alegand (in orice ordine doriti) o submultime a perechilor date.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere a si b ale unei perechi.
- Date de iesire
- Se afiseaza un singur numar: lungimea maxima a unui lant de perechi.
- Restrictii
- 1 <= n <= 1000, -10^6 <= a < b <= 10^6
Exemple
Exemplul 1
Intrare
3 1 2 2 3 3 4
Iesire
2
Exemplul 2
Intrare
4 -10 -8 8 9 -5 0 6 10
Iesire
3