Pe o axa exista n baloane, fiecare reprezentat printr-un interval [inceput, sfarsit]. O sageata trasa vertical la o coordonata x sparge toate baloanele al caror interval contine x (inclusiv capetele). Determinati, folosind metoda Greedy, numarul minim de sageti necesare pentru a sparge toate baloanele.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: inceputul si sfarsitul intervalului unui balon.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de sageti necesare.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput <= sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
4 10 16 2 8 1 6 7 12
Iesire
2
Exemplul 2
Intrare
1 1 2
Iesire
1