== include(page="template/taskheader" task_id="posta") ==
Poveste şi cerinţă...
Lance s-a anagajat recent la posta, iar slujba sa consta in sortarea scrisorilor primite. Scrisorile sosesc printr-un dispozitiv special cu mai multe sertare asezate in linie unul dupa altul si numerotate incepand cu $0$. Pentru a-si face viata mai usoara, Lance vrea sa cumpere niste vagoane de colectare care sa il ajute sa adune toate scrisorile care sosesc prin dispozitiv. Deoarece este criza, Lance doreste sa minimeze numarul vagoanelor de care are nevoie.
Pentru a se deplasa intre doua sertare consecutive, unui vagon ii este necesara o secunda. Mai mult, la inceputul zilei, Lance poate pozitiona vagoanele oriunde doreste. Stiind ca in total sunt $N$ scrisori, si cunoscand pentru fiecare dintre acestea sertarul si momentul de timp la care soseste, gasiti numarul minim de vagoane de colectare necesare. Trebuie luat in calcul faptul ca Lance doreste ca pentru fiecare scrisoare colectarea sa se faca instantaneu, adica sa existe un vagon in dreptul sertarului in momentul sosirii.
h2. Date de intrare
Fişierul de intrare $posta.in$ ...
Fisierul de intrare $posta.in$ contine pe prima linie numarul $N$ al scrisorilor primite. Urmatoarele $N$ linii contin cate $2$ numere $S$~i~ si $T$~i~ reprezentand sertarul, respectiv timpul la care soseste cate o scrisoare.
h2. Date de ieşire
h2. Date de iesire
În fişierul de ieşire $posta.out$ ...
Pe prima linie a fisierului de iesire $posta.out$ veti afisa un singur numar $V$, reprezentand numarul minim de vagoane necesare. Pe urmatoarea linie se vor gasi $N$ numere intregi intre $1$ si $V$, reprezentand vagoanele asociate scrisorilor in oridinea din fisierul de intrare.
h2. Restricţii
h2. Restrictii si precizari
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100000$
* $0 ≤ S{~i~}, T{~i~} ≤ 10^9^$
* Daca exista mai multe solutii poate fi afisata oricare
h2. Exemplu
table(example). |_. posta.in |_. posta.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
1 1
2 4
3 3
4 1
| 2
1 2 1 2
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="posta") ==
