24229번 - 모두싸인 출근길

문제

취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까?

다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ $L,ドル $R$ ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 끝점에도 착지가 가능하다. 주헌이가 한 번의 점프로 건너갈 수 있는 최대 거리는 마지막으로 착지한 시점 이후로 건너간 거리와 같다. 단, 점프를 한 적이 없으면 출발한 시점 이후로 건너간 거리와 같다. 예를 들어 주헌이가 점프를 해서 좌표 9에 착지했고 12에서 다시 점프를 한다면, 점프할 수 있는 거리는 최대 3이다.

주헌이가 이동할 수 있는 가장 먼 지점을 구해보자. 단, 점프를 했는데 판자 위에 착지하지 못한 경우는 이동하지 않은 것으로 간주한다.

입력

첫째 줄에 판자의 개수 $N$이 주어진다. $( 1 ≤ N ≤ 200,000 )$

둘째 줄부터 $N$개의 줄에 걸쳐서 판자가 놓인 구간을 나타내는 정수 $L,R$이 각각 주어진다. $( 0 ≤ L < R ≤ 10^9 )$

$L = 0$인 판자가 적어도 하나는 주어진다.

출력

주헌이가 최대로 멀리 이동할 수 있는 지점의 좌표를 출력한다.

제한

힌트