社團教室借用

題目敘述

社團教室一天只有一間，現在有 n 筆借用申請，每筆申請佔用半開時間區間 [s,e)。同一時間教室只能給一個社團使用，請算出最多能接受幾筆互不重疊的申請。

輸入格式

• 第 1 行：整數 n。
• 接下來 n 行，每行兩個整數 s、e，代表一個區間 [s,e)。

輸出格式

輸出一個整數，表示最多能選出的區間數量。

限制

• 1 ≤ n ≤ 2· 10⁵
• 0 ≤ s < e ≤ 10⁹

範例

範例 1

輸入

3
1 4
2 3
4 6

輸出

2

範例 2

輸入

1
0 1

輸出

1

說明

區間是半開的，所以一個區間的結束時刻剛好等於另一個區間的開始時刻時，兩者不算重疊，可以同時選。