Für wachsende Bedürfnisse von $N$ Kühen ($1 \le N \le 50,000$) kauft Farmer John einen Limonadenautomaten und sucht den besten Standort.

Weide als Zahlengerade. Kuh $i$ grast in $A_i..B_i$ ($1 \le A_i \le B_i; A_i \le B_i \le 1,000,000,000$), Endpunkte eingeschlossen. Automat an jedem ganzzahligen Punkt von $1..1,000,000,000$. Faule Kühe wollen möglichst wenig gehen und ihn im eigenen Intervall.

Nicht immer alle zufriedenstellbar. FJ sucht maximale Zahl zufriedener Kühe.

Vier Intervalle $3..5$, $4..8$, $1..2$, $5..10$ sind unten dargestellt:

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

Erste, zweite, vierte teilen $5$, dritte ist disjunkt. Höchstens 3 haben ihn im Intervall.

Eingabe

• Zeile 1: Ganzzahl $N$.
• Zeilen $2..N+1$: Zeile $i+1$, zwei Ganzzahlen $A_i$, $B_i$ durch Leerzeichen getrennt.

Ausgabe

• Zeile 1: Ganzzahl, maximale Kuhzahl mit gemeinsam möglichem Automatenstandort in allen Intervallen.

Beispiele

Eingabe 1

4
3 5
4 8
1 2
5 10

Ausgabe 1

3

Hinweis

Bei $5$ sind 1, 2, 4 zufrieden; alle vier unmöglich.

Aufgabenautor: Neal Wu, 2008.