Festival P73935

Statement

Un festival de cinema projectarà $n$ pel·lícules, totes en sales diferents. Un diari vol fer una crònica de cada pel·lícula, i per això hi enviarà tants experts com calgui. Les pel·lícules s’han de veure senceres. A més, si una pel·lícula comença en el mateix instant que una altra acaba, un sol expert no en podrà veure les dues, perquè no tindrà temps de canviar de sala.

Podeu calcular el mínim nombre d’experts que el diari haurà d’enviar al festival?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ , seguits d’ $n$ parells $c$ $a$ , amb $c < a$ , indicant una pel·lícula que comença en l’instant $c$ i que acaba en l’instant $a$ . Suposeu $1 \le n \le 10^5$ , i que tots els instants són nombres enters entre 0 i $10^9$ .

Sortida

Per a cada cas, escriviu el mínim nombre d’experts que cal enviar al festival.

Public test cases

Input

3  0 1  4 5  2 3
3  0 1  2 3  1 2
4  10 20  5 100  20 70  20 200
2  0 1000000000  0 1000000000

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++ Python
User solutions: C++ Python