На числовой прямой даны \(n\) отрезков. Назовём
глубиной отрезка \(i\) количество отрезков
\(j\) (включая сам отрезок \(i\)),
которые целиком его содержат: \(l_j \le l_i\)
и \(r_i \le r_j\).
Найдите максимальную глубину среди всех данных отрезков.
Формат входных данных
В первой строке — целое число \(n\)
(\(1 \le n \le 5000\)).
В каждой из следующих \(n\) строк — два целых числа
\(l_i\) и \(r_i\)
(\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Одно целое число — максимальная глубина.
Примечание
В первом примере отрезок \([3, 4]\) содержится в
\([2, 5]\), который, в свою очередь, содержится в
\([1, 10]\). Глубина \([3, 4]\)
равна \(3\): его содержат он сам, \([2, 5]\)
и \([1, 10]\). Это максимум.
Во втором примере все три отрезка совпадают, и каждый «содержится» в каждом —
глубина равна \(3\).
| № | Входные данные | Выходные данные |
|
1
|
4
1 10
2 5
3 4
6 9
|
3
|
|
2
|
3
0 5
0 5
0 5
|
3
|