==Include(page="template/taskheader" task_id="granita")==
 
==Include(page="template/raw")==
 
Granita
 
 
 
La granita statului A cu statul B se afla N dispozitive de aparare. Pentru fiecare dispozitiv k se cunoaste intervalul de lungime [A[k], B[k]] in care actioneaza (granita se considera a fi o linie dreapta, iar fiecare dispozitiv acopera un anumit segment de pe aceasta linie). Pentru a reduce costurile de intretinere, presedintele statului A a decis ca unele dintre cele N dispozitive de aparare sa fie desfiintate. Mai precis, vor fi desfiintate dispozitivele redundante. Un dispozitiv i este redundant, daca exista cel putin un alt dispozitiv j, astfel incat intervalul [A[i], B[i]] sa fie inclus in intervalul [A[j], B[j]] (adica A[j]<A[i] si B[i]<B[j]).
 
h2. Cerinta
 
Determinati cate dintre cele N dispozitive de aparare sunt redundante.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare granita.in se afla numarul intreg N, reprezentand numarul dispozitivelor de aparare. Pe urmatoarele N linii se afla cate doua numere intregi, a si b (a<b), reprezentand capetele intervalelor in care actioneaza fiecare dispozitiv.
 
h2. Date de Iesire
 
In fisierul de iesire granita.out contine o singura linie pe care veti afisa un singur numar intreg, reprezentand numarul dispozitivelor redundante.
 
h2. Restrictii
 
. 1 <= N <= 16.000
 
. 0 <= A[i] < B[i] <= 2.000.000.000
 
. Toate numerele A[i] vor fi diferite intre ele
 
. Toate numerele B[i] vor fi diferite intre ele
 
 
 
Exemple
 
 
|granita.in |granita.out |

==Include(page="template/taskheader" task_id="granita")==
 
La granita statului A cu statul B se afla $N$ dispozitive de aparare. Pentru fiecare dispozitiv $k$ se cunoaste intervalul de lungime $[A{~k~}, B{~k~}]$ in care actioneaza (granita se considera a fi o linie dreapta, iar fiecare dispozitiv acopera un anumit segment de pe aceasta linie). Pentru a reduce costurile de intretinere, presedintele statului A a decis ca unele dintre cele $N$ dispozitive de aparare sa fie desfiintate. Mai precis, vor fi desfiintate dispozitivele redundante. Un dispozitiv $i$ este redundant, daca exista cel putin un alt dispozitiv $j$, astfel incat intervalul $[A{~i~}, B{~i~}]$ sa fie inclus in intervalul $[A{~j~}, B{~j~}]$ (adica $A{~j~}<A{~i~}$ si $B{~i~}<B{~j~}$).
 
h2. Cerinta
 
Determinati cate dintre cele $N$ dispozitive de aparare sunt redundante.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare $granita.in$ se afla numarul intreg $N$, reprezentand numarul dispozitivelor de aparare. Pe urmatoarele N linii se afla cate doua numere intregi, $a$ si $b (a<b)$, reprezentand capetele intervalelor in care actioneaza fiecare dispozitiv.
 
h2. Date de Iesire
 
In fisierul de iesire $granita.out$ contine o singura linie pe care veti afisa un singur numar intreg, reprezentand numarul dispozitivelor redundante.
 
h2. Restrictii
 
* $1 &le; N &le; 16.000$
* $0 &le; A{~i~} < B{~i~} &le; 2.000.000.000$
* Toate numerele $A{~i~}$ vor fi diferite intre ele
* Toate numerele $B{~i~}$ vor fi diferite intre ele
 
h2. Exemple
 
table(example). |_. granita.in |_. granita.out |
|5
0 10
2 9
3 8
1 15
6 11 | 3 |
 
h3. Explicatie
 
Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.
 
==Include(page="template/taskfooter" task_id="granita")==

|5 |3 |
|0 10 | |
|2 9 | |
|3 8 | |
|1 15 | |
|6 11 | |
Explicatie:
Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.
==Include(page="template/taskfooter" task_id="granita")==

480