선물 구매

어린 사샤에게는 여자 친구가 두 명 있습니다. 사샤는 3월 8일을 맞아 두 친구에게 선물로 기쁨을 주고 싶어 합니다. 그래서 도시에서 가장 큰 쇼핑센터에 갑니다.

쇼핑센터에는 $n$개의 부서가 있고, 각 부서에는 정확히 두 개의 가게가 있습니다. 부서는 1번부터 $n$번까지 번호를 매깁니다. $i$번째 부서의 첫 번째 가게에서 파는 선물은 $a_i$루블, 두 번째 가게에서 파는 선물은 $b_i$루블입니다.

사샤는 모든 부서를 한 번씩 방문하며, 각 부서에서는 정확히 한 가게에 들어갑니다. 즉 $i$번째 부서에 도착하면 다음 중 하나를 정확히 한 번 합니다.

1. 첫 번째 친구에게 줄 선물을 $a_i$루블을 주고 삽니다.
2. 두 번째 친구에게 줄 선물을 $b_i$루블을 주고 삽니다.

사샤는 두 친구 각각에게 선물을 최소 하나씩 사려고 합니다. 또한 두 친구에게 준 선물 중 가장 비싼 선물의 가격 차이가 최대한 작아지도록 고르려고 합니다. 누구도 서운해하지 않게 하기 위해서입니다.

정식으로 표현하면, $m_1$은 첫 번째 친구에게 산 선물 중 최고 가격이고, $m_2$는 두 번째 친구에게 산 선물 중 최고 가격입니다. 사샤는 $\lvert m_1 - m_2 \rvert$를 최소로 만들도록 선물을 고릅니다.

첫 줄에 정수 $n$ ($2 \le n \le 500\,000$)이 주어집니다. 부서의 수입니다. 이어지는 $n$개의 줄에는 각각 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i \le 10^9$)가 주어집니다. 이는 $i$번째 부서의 첫 번째 가게와 두 번째 가게의 선물 가격입니다.

두 친구에게 산 선물 중 가장 비싼 가격의 차이가 가질 수 있는 최솟값을 정수 하나로 출력합니다.

첫 번째 예제에서 사샤에게는 두 가지 선택이 있습니다. 첫 번째 부서에서 첫 친구의 선물을, 두 번째 부서에서 둘째 친구의 선물을 사는 경우와 그 반대인 경우입니다. 전자의 경우 $m_1 = m_2 = 1$이고, 후자의 경우 $m_1 = m_2 = 2$입니다. 두 경우 모두 답은 0입니다.

두 번째 예제에서는 첫 친구에게 2, 4, 5번 부서의 선물을, 둘째 친구에게 1번과 3번 부서의 선물을 줍니다. 따라서 $m_1 = \max(2, 4, 2) = 4$, $m_2 = \max(5, 3) = 5$이고, 답은 $\lvert 4 - 5 \rvert = 1$입니다.