#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Activity Selection - Classic Problems | Repovive

CLS51. Activity Selection

2s256 MB

Given $n$ half-open intervals $[l_i, r_i)$ , choose the maximum number of intervals so that no two chosen intervals overlap.

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le l_i < r_i \le 10^9$
Intervals that touch at an endpoint do not overlap.

Input

\begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array}

Output

count_{\max}

Samples

Input

Explanation

Choosing [1,3), [3,6), and [6,8) gives 3 non-overlapping intervals.

Output

Input

Explanation

The intervals [1,2) and [2,3) can both be chosen, so the answer is 2.

Output

Input

Explanation

One maximum choice is [2,3), [3,5), and [7,9), giving 3.

Output

Given $n$ half-open intervals $[l_i, r_i)$ , choose the maximum number of intervals so that no two chosen intervals overlap.

$1 \le n \le 2 \cdot 10^5$
$0 \le l_i < r_i \le 10^9$
Intervals that touch at an endpoint do not overlap.

\begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array}

count_{\max}