SPOJ in Gyumri

   Даны N заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия (s_i и f_i соответственно для i-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i и j совместны (не пересекаются), если интервалы [s_i,f_i) и [s_j,f_j) не пересекаются (то есть fi ≤ sj или fj≤si). Задача состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Входные данные.

   N– Количество заявок (1 ≤ N ≤ 200000).

   S[1] F[1]

   S[2] F[2]

   …

   S[N] F[N]

   S[i] F[i] – описание i-ой заявки (0 ≤S[i] < F[i] ≤ 100000000).

   Все числа целые.

Выходные данные.

   Ans – ответ на задачу – максимальное количество совместных друг с другом заявок.

Пример.