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

Програмування – це мистецтво!

Програмування – це мистецтво!

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

На питання слухочів Зимової Школи 2011: яка у нього заробітна плата, Петро Мітрічев відповів дуже політкоректно:

– У порівнянні з L – багато, а ось у порівнянні з R ­– мало.

Про те, хто ж такі були ці загадкові L і R, Петро дипломатично промовчав…

Думаючи про те, що б такого цікавого розповісти слухачам Зимової школи 2011 у м. Харкові, Петро посилено перебирав можливі варіанти тематики, але практично відразу ж їх відкидав, так як теми весь час приходили на думку вже давно відомі і кемось раніше розповідались. Але як справжній художник-програміст, який вільно володіє фігурами вищого пілотажу у цій справі, він не міг собі дозволити вибрати якусь ординарну тему.

А розповіям я їм про L і R ­– тим більше, що про це, здається, ще ніхкто не розповідав, – подумав Петро і почав малювати план лекції і накидувати схеми задачок. Благо у фірмі, де він працював, був великий запас маркерів різних кольорів, і схеми він почав малювати саме ними. Якщо йому щось у схемі не подобалось, Петро поступав дуже просто: він брав маркер іншого кольору і замальовував ним місце, яке йому не сподобалось, зверху новим кольором, який відповідав новому пункту плана.

Перемальовуючи таким чином схему, він дуже швидко помітив, що і цей процес можна запропонувати у вигляді задачки.

Деякий програміст використовує для малювання на координатній прямій N відрізків N маркерів різних кольорів. Знаючи ліві (L) та праві (R) кінці кожного намальованого відрізка, визнаичти максимальну кількість різних кольорів, які можна отримати у кінцевому варіанті рисунка. Цю кількість назвемо рівнем цього художника-програміста.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число N (1N300). У наступних N рядках задано N пар чисел L і R через пропуск (-10^9L_i < R_i10^9).

Вихідні дані

Вивести єдине число: шуканий найбільший рівень художника-програміста.

Приклад

Вхідні дані #1
4
1 3
2 4
2 3
1 4
Вихідні дані #1
3