最多筆不衝突的借用申請

題目敘述

社團辦公室同一時間只能讓一個活動使用。現在收到 n 筆借用申請，第 i 筆要求使用的時段是半開區間 [s_i, e_i)，也就是從時刻 s_i 開始、到時刻 e_i 結束；某一筆在 e_i 結束的那一刻，另一筆可以立刻接著開始，不算衝突。

請挑出彼此時段都不重疊的申請，並輸出最多能挑幾筆。

輸入格式

第一行有一個整數 n。接下來 n 行，每行兩個整數 s_i 與 e_i。當 n = 0 時只有第一行。

輸出格式

輸出一個整數，代表最多能同時接受的申請數。

限制

• 0 ≤ n ≤ 10⁵
• 0 ≤ s_i < e_i ≤ 10⁹

範例

範例 1

輸入

4
1 4
3 5
0 6
5 7

輸出

2

範例 2

輸入

0

輸出

0

範例 3

輸入

3
1 2
2 3
3 4

輸出

3

範例 4

輸入

3
1 10
2 3
4 5

輸出

2

範例 5

輸入

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

輸出

4

範例 6

輸入

1
1 2

輸出

1

說明

• 範例 1：四筆申請依結束時刻排好是 [1,4)、[3,5)、[0,6)、[5,7)。接受 [1,4) 後，[3,5) 與 [0,6) 都與它重疊；[5,7) 在時刻 5 開始，晚於 4，可以接受。共 2 筆。
• 範例 2：沒有任何申請，答案為 0。
• 範例 3：三筆首尾相接：[1,2)、[2,3)、[3,4)。因為是半開區間，結束與開始同一刻不衝突，三筆都能接受。
• 範例 4：接受 [2,3) 與 [4,5) 共 2 筆；若先接受很長的 [1,10)，就只能接受這一筆。
• 範例 5：較大的一組資料：依結束時刻挑選，可接受 [1,4)、[5,7)、[8,11)、[12,14) 共 4 筆。
• 範例 6：只有一筆申請，直接接受，答案為 1。