Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета l
i и моментом конца r
i (l
i ≤ r
i).
Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?
Никакие два принятых заказа не могут пересекаться, то есть не должно существовать момента времени, который принадлежит сразу двум принятым заказам. Если один из заказов начинается в момент, когда заканчивается другой, то они не могут быть приняты вместе.
Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел l
i, r
i (0 ≤ l
i ≤ r
i ≤ 10
9).
Выходные данные:
Выведите наибольшее количество заказов, которые могут быть приняты.
Примеры:
| Входные данные |
Выходные данные |
2
7 11
4 7 |
1 |
5
1 2
2 3
3 4
4 5
5 6 |
3 |
6
4 8
1 5
4 7
2 5
1 3
6 8 |
2 |