eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Відрізки

Відрізки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задано відрізки на прямій. Яку максимальну кількість відрізків можна вибрати так, щоб жодні два з них не перетинались? Відрізки вважаються відкритими.

Вхідні дані

У першому рядку задано кількість відрізків n~(1 \le n \le 10^5). У наступнихn рядках описано відрізки: i-ий рядок містить два цілих числа l_i та r_i~(1 \le l_i < r_i \le 10^9) — координати початку та кінця відрізка.

Вихідні дані

Виведіть максимальну кількість відрізків, що не перетинаються.

Приклад

Вхідні дані #1
5
1 4
3 8
7 8
2 5
4 6
Вихідні дані #1
3
Вхідні дані #2
4
1 3
2 6
1 8
2 5
Вихідні дані #2
1