카라반 강도단

먼 옛날 아주 먼 나라에 두 거대 도시가 있었고, 그 사이를 대상로(Great Caravan Road)가 이었다. 이 길에서는 여러 강도단이 '활동'했다.

오래된 관습에 따라, $i$번째 강도단은 대상로의 $a_i$ 마일 지점부터 $b_i$ 마일 지점 사이를 지나는 모든 상인을 털었다. 이 관습은 오래되었지만 영리했다. 서로 다른 두 강도단 $i$, $j$ 중에서 $a_i \le a_j$이면서 $b_j \le b_i$인 경우, 즉 한 구간이 다른 구간을 포함하는 경우가 결코 없었기 때문이다. 그래도 두 강도단의 구간이 겹치면 이따금 피비린내 나는 다툼이 벌어졌다.

싸움을 끝내기 위해 강도단 두목들은 각 강도단에게 새 구간을 다시 배정하기로 했다. 새 구간은 다음을 모두 만족해야 한다.

• 모든 새 구간은 서로 겹치지 않는다(유혈을 피하기 위해).
• 각 강도단의 새 구간은 원래 구간의 부분구간이다(오래된 관습을 지키기 위해).
• 모든 새 구간의 길이는 같다(공평을 위해).

이렇게 다시 배정했을 때 각 강도단이 가질 수 있는 구간 길이의 최댓값을 구하라.

첫 줄에 강도단의 수 $n$ ($1 \le n \le 100000$)이 주어진다.

이어지는 $n$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($0 \le a_i < b_i \le 1000000$)가 주어지며, 한 강도단의 구간을 나타낸다. 입력은 위에서 설명한 조건을 만족한다. 즉, 어떤 구간도 다른 구간을 포함하지 않는다.

다시 배정한 뒤 가질 수 있는 공통 구간 길이의 최댓값을 마일 단위로, 기약분수 $p/q$ 꼴로 출력한다.

강도단 $(2, 6)$, $(1, 4)$, $(8, 12)$로 이루어진 예제에서, 모든 강도단에게 길이 $5/2$의 구간을 주는 한 가지 최적 재배정은 다음과 같다.

• 첫째 강도단은 $[7/2, 6] = [3.5, 6]$을 가지며, 이는 원래 구간 $(2, 6)$의 부분구간이다.
• 둘째 강도단은 $[1, 7/2] = [1, 3.5]$을 가지며, 이는 원래 구간 $(1, 4)$의 부분구간이다.
• 셋째 강도단은 $[8, 21/2] = [8, 10.5]$를 가지며, 이는 원래 구간 $(8, 12)$의 부분구간이다.