Pour les besoins croissants de $N$ vaches ($1 \le N \le 50,000$), Farmer John achète un distributeur de sodas et cherche l'emplacement idéal.

Le pâturage est une droite numérique. La vache $i$ broute dans $A_i..B_i$ ($1 \le A_i \le B_i; A_i \le B_i \le 1,000,000,000$), bornes incluses. Machine à toute position entière de $1..1,000,000,000$. Très paresseuses, elles bougent le moins possible et veulent la machine dans leur intervalle.

Pas toujours possible de satisfaire toutes. FJ veut le plus grand nombre satisfait.

Quatre intervalles $3..5$, $4..8$, $1..2$, $5..10$ sont illustrés ci-dessous :

         1   2   3   4   5   6   7   8   9  10  11  12  13
         |---|---|---|---|---|---|---|---|---|---|---|---|-...
                 aaaaaaaaa
                     bbbbbbbbbbbbbbbbb
         ccccc           ddddddddddddddddddddd

Les première, deuxième, quatrième partagent $5$ ; la troisième est disjointe. Au maximum 3 ont la machine dans leur intervalle.

Entrée

• Ligne 1 : entier $N$.
• Lignes $2..N+1$ : ligne $i+1$, deux entiers $A_i$, $B_i$ séparés par espace.

Sortie

• Ligne 1 : un entier, maximum de vaches dont les intervalles peuvent tous contenir la machine.

Exemples

Entrée 1

4
3 5
4 8
1 2
5 10

Sortie 1

3

Remarque

À $5$, vaches 1, 2, 4 satisfaites ; Il est impossible de satisfaire les quatre.

Auteur du problème : Neal Wu, 2008.