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

Minimum Meeting Rooms - Classic Problems | Repovive

CLS62. Minimum Meeting Rooms

2s256 MB

Given meeting intervals $[l_i, r_i)$ , find the minimum number of rooms needed so every meeting can be scheduled.

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le l_i < r_i \le 10^9$
Meetings ending at time $t$ free their room for meetings starting at time $t$ .

Input

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

Output

rooms_{\min}

Samples

Input

Explanation

The first meeting overlaps each of the other two, so two rooms are enough and necessary.

Output

Input

Explanation

Meetings that touch at endpoints can reuse the same room, so one room is enough.

Output

Input

Explanation

At time 4, three meetings are active, so the answer is 3.

Output

Given meeting intervals $[l_i, r_i)$ , find the minimum number of rooms needed so every meeting can be scheduled.

$1 \le n \le 2 \cdot 10^5$
$0 \le l_i < r_i \le 10^9$
Meetings ending at time $t$ free their room for meetings starting at time $t$ .

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

rooms_{\min}