На числовой прямой нарисованы \(n\) отрезков. Концы отрезков
заданы целыми числами. Точка \(x\) считается принадлежащей
отрезку \([s, f]\), если \(s \le x \le f\)
(концы включены).
Найдите такую целую точку \(x\), которой одновременно
принадлежит максимальное количество данных отрезков. Если таких точек несколько,
выведите наименьшую из них.
Формат входных данных
В первой строке записано целое число \(n\)
(\(1 \le n \le 10^5\)) — количество отрезков.
В каждой из следующих \(n\) строк записаны два целых числа
\(s_i\) и \(f_i\)
(\(-10^9 \le s_i \le f_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Выведите два целых числа через пробел: максимальное количество отрезков, накрывающих одну
точку, и наименьшую целую точку, в которой этот максимум достигается.
Примечание
В первом примере отрезки \([0,1]\),
\([0,2]\), \([1,2]\).
Точка \(x = 1\) принадлежит всем трём отрезкам, и это
наименьшая такая точка.
Во втором примере точка \(x = 1\) принадлежит
двум отрезкам: \([0,1]\) и \([1,3]\).
Это максимум, достигаемый раньше всего на прямой.
| № | Входные данные | Выходные данные |
|
1
|
3
0 1
0 2
1 2
|
3 1
|
|
2
|
3
0 1
1 3
-100 -99
|
2 1
|