Start: May, 25, 2022 18:00:00
2022春acm通识课期末考补题
End: May, 25, 2025 22:00:00
Time elapsed:
Time remaining:

拒绝躺平

Time Limit:  1 s      Memory Limit:   64 MB
Submission:97     AC:22     Score:0

Description

     众所周知,"躺平"是非常不好的,因为躺平之后大家可能会重叠在一起而感觉不舒服甚至引发冲突!现在有$N$个人想要"躺平"在$x$轴上,给定他们每个人躺平后的区间$[L_i,R_i]$,王图北同学想要知道最多可以从中选几个人,使他们躺平之后不会引起冲突,(即区间不相交),聪明的你可以告诉他答案吗?

  
注意 :如果小舟学长躺平在区间$[3,4]$,而小殷学长躺平在区间$[4,5]$,那么大事不妙!因为在$x=4$处小舟学长的脚翘到了小殷学长的头上!

Input

第一行一个整数 $ N(1 \leqslant N \leqslant 10^5) $,代表总人数,接下来N行每行输入$ L_i $ 和$ R_i (-10^9 \leqslant L_i \leqslant R_i \leqslant 10^9)$,代表第$i$个人所占的区间。

Output

输出一个整数,表示所选区间不相交情况下人数的最大值。

Samples

input
3 -1 1 2 4 3 5
output
2