Відрізки

Обмеження: 2 сек., 256 МіБ

Дано множину \(S\) із \(n\) відрізків. Відрізки лежать на координатній прямій та \(i\)-тий відрізок займає проміжок \([a_i, b_i]\).

За означенням, проміжок \([l_1, r_1]\) містить проміжок \([l_2, r_2]\), якщо виконується \(l_1 \le l_2 < r_2 \le r_1\).

У цій задачі потрібно знайти розмір найбільшої підмножини \(S\), у якій жоден із відрізків не буде містити іншого.

Вхідні дані

У першому рядку дано одне ціле число \(n\) — кількість відрізків.

У наступних \(n\) рядках дано по два цілі числа \(a_i\) та \(b_i\) — координати початку і кінця \(i\)-того відрізка.

Вихідні дані

У єдиному рядку виведіть ціле число — максимальний розмір підмножини.

Обмеження

40% тестів: \(1 \le n \le 100\),

60% тестів: \(100 \le n \le 10^5\),

\(1 \le a_i < b_i \le 10^9, i = 1..n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 2 5 1 4 1 6 3 8	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 5 8 3 7 4 10 12 15 1 7	3

Примітки

У першому тесті можна отримати відповідь 3, обравши перший, другий і четвертий відрізки.