Maximizing Non-Overlapping Grazing Intervals

Farmer John has N cows (1 \(\leq N \leq 50,000\)) and a one-dimensional pasture. Each cow \(i\) prefers to graze in a specific interval \((S_i, E_i)\) on the number line, where \(1 \leq S_i < E_i \leq 10^8\). Since the cows are selfish, no two cows want to share any grazing area. That is, two cows \(i\) and \(j\) can graze at the same time only if either \(S_i \geq E_j\) or \(E_i \leq S_j\).

Your task is to determine the maximum number of cows that can graze simultaneously without overlapping their preferred intervals.

Example:

Input:
5
2 4
1 12
4 5
7 10
7 8
Output:
3

In the example, one optimal solution is for cows with intervals \((2,4)\), \((4,5)\), and \((7,10)\) (or \((7,8)\)) to graze together.

Note: If a cow grazing interval is chosen, then any other interval that overlaps with it (i.e. not satisfying \(S_i \geq E_j\) or \(E_i \leq S_j\)) cannot be chosen.

inputFormat

The first line contains an integer \(N\), the number of cows. Each of the next \(N\) lines contains two integers \(S_i\) and \(E_i\), representing the start and end of the \(i\)th cow's preferred grazing interval.

outputFormat

Output a single integer: the maximum number of cows that can graze simultaneously without overlapping their intervals.

sample

5
2 4
1 12
4 5
7 10
7 8

3