一家餐厅收到 n 个租赁订单。每个租赁订单都会在连续一段时间内预订餐厅,第 i 个订单由两个时间值来表征 - 开始时间 li 和结束时间 ri (li ≤ ri)。
餐厅管理层可以接受和拒绝订单。餐厅最多可以接受多少订单?
两个已接受的订单不能相交,即它们不能共享哪怕是片刻的时间。如果一个订单在另一个订单开始时结束,则不能同时接受这两个订单。
输入
第一行包含整数 n (1 ≤ n ≤ 5·105) — 订单数。以下 n 行分别包含整数值 li 和 ri (1 ≤ li ≤ ri ≤ 109)。
输出
打印可以接受的最大订单数。
示例
输入 #1
2 7 11 4 7
输出 #1
1
输入 #2
5 1 2 2 3 3 4 4 5 5 6
输出 #2
3
输入 #3
6 4 8 1 5 4 7 2 5 1 3 6 8
输出 #3
2