Să considerăm N segmente pe axa OX, colorate distinct. Pentru fiecare segment se cunoaşte extremitatea iniţială şi extremitatea finală.
Segmentele pot fi desenate în orice ordine. Când un segment este desenat peste un alt segment, rămâne vizibil integral doar segmentul de deasupra.

Cerinţă

Determinaţi numărul maxim de culori vizibile după desenarea celor N segmente într-o ordine convenabilă.

Date de intrare

Fişierul de intrare maxviz.in conţine pe prima linie numărul natural N, reprezentând numărul de segmente. Pe următoarele N linii se află cele N segmente, câte un segment pe o linie. Pentru fiecare segment sunt specificate două  numere întregi separate prin spaţiu st dr, reprezentând extremitatea iniţială, respectiv extremitatea finală a segmentului.

Date de ieşire

Fişierul de ieşire maxviz.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de culori vizibile după desenarea într-o ordine convenabilă a celor N segmente.

Restricţii

• 1 ≤ N ≤ 300
• -1000 000 000 ≤ st < dr ≤ 1000 000 000

Exemple

maxviz.in	maxviz.out
4 10 30 20 40 20 30 10 40	3

prof. Emanuela Cerchez

Colegiul Naţional "Emil Racoviţă" Iaşi

emanuela.cerchez@gmail.com