Description

Each of Farmer John’s $N$ cows ($1 \le N \le 50{,}000$) likes to graze in a specific part of the pasture, which can be modeled as a large one-dimensional number line. Cow $i$’s favorite grazing range starts at location $S_i$ and ends at location $E_i$ ($1 \le S_i < E_i \le 100{,}000{,}000$).

Cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows $i$ and $j$ can graze at the same time only if $S_i \ge E_j$ or $E_i \le S_j$. Farmer John would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.

Consider a set of 5 cows with ranges shown below:

  ... 1    2    3    4    5    6    7    8    9   10   11   12   13 ...
  ... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1:      <===:===>          :              :              :
Cow 2: <========:==============:==============:=============>:
Cow 3:          :     <====>   :              :              :
Cow 4:          :              :     <========:===>          :
Cow 5:          :              :     <==>     :              :

These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively.

As a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.

Input Format

• Line 1: A single integer $N$.
• Lines 2..$N+1$: Line $i+1$ contains two space-separated integers $S_i$ and $E_i$.

Output Format

• Line 1: A single integer representing the maximum number of cows that can graze at once.

5 
2 4 
1 12 
4 5 
7 10 
7 8 

3 

Hint

Translated by ChatGPT 5