В актовом зале школы может проходить только одно мероприятие в каждый момент времени. На проведение актового зала подано \(n\) заявок от разных кружков. Каждая заявка — это интервал времени \([l_i; r_i]\): кружок хочет занять зал с минуты \(l_i\) по минуту \(r_i\) включительно.
Два кружка не могут проходить в зале одновременно: если один занимает время \([l_1; r_1]\), а другой — \([l_2; r_2]\), эти интервалы не должны пересекаться. Если один кружок заканчивается ровно в ту минуту, когда начинается другой, это тоже считается пересечением.
Директор хочет одобрить как можно больше заявок. Какое максимальное количество кружков можно разместить в зале за день?
Формат входных данных
В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество заявок.
В следующих \(n\) строках — по два целых числа \(l_i\) и \(r_i\) (\(0 \le l_i < r_i \le 10^9\)) — время начала и время окончания каждой заявки.
Формат выходных данных
Одно целое число — максимальное количество заявок, которые можно одобрить.
Примечание
В первом примере можно одобрить заявки \([1; 3]\) и \([4; 7]\) — они не пересекаются.
Во втором примере оптимально взять \([2; 3]\) и \([5; 7]\).
| № | Входные данные | Выходные данные |
|
1
|
4
1 3
2 5
4 7
6 9
|
2
|
|
2
|
5
1 4
2 3
3 5
5 7
6 8
|
2
|