웨이팅

시간 제한1초메모리 제한1024 MB

요약

한 시간에 한 명만 입장하는 식당에서 손님이 도착한 뒤 입장할 때까지 기다린 시간의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 정렬, 큐, 그리디
정답자: 아직 제출이 없습니다

문제

테이블이 1개 있는 24시간 맛집이 있다. 이 식당은 예약제로 운영되며 1시간에 오직 1명의 예약을 받는다.

어느 날, 식당 사장님은 예약하고도 제때 오지 않는 손님들이 많아 다음과 같은 규칙을 만들었다.

식당 입장은 매 정각에 이루어지며, 식당에 입장한 손님은 1시간 뒤에 퇴장한다.
자신의 예약 시간이 아닌 시간에 도착한 손님들은 대기 줄에 선다. 동시에 도착한 손님들은 예약 시간이 빠른 순으로 선다.
자신의 예약 시간에 늦지 않게 도착한 손님은 예약 시간이 되면 먼저 입장한다.
예약이 없거나 예약자가 도착하지 않았다면 대기 줄의 첫 번째 손님이 입장한다.

대기 줄에 있는 손님들은 인내심이 뛰어나기 때문에 식당에 입장할 때까지 줄을 이탈하지 않는다.

각 손님이 예약한 시각 $t\_1$ 과 도착한 시각 $t\_2$ 가 주어졌을 때, 식당에 도착해 입장할 때까지 가장 오래 기다린 손님이 몇 시간을 기다렸는지 구하여라.

입력

첫 번째 줄에 예약한 손님의 수 $N$ 이 주어진다. $(1 \leq N \leq 100\\,000)$

두 번째 줄부터 각 사람이 예약한 시각 $t\_1$ 과 도착한 시각 $t\_2$ 가 공백으로 구분되어 주어진다. $t\_1$ 과 $t\_2$ 는 규칙을 도입한 첫 정각으로부터 몇 단위 시간이 지났는지를 의미한다. $t\_1$ 과 $t\_2$ 는 모두 정수이며 $t\_1$ 은 서로 다르다. $(1 \leq t\_1, t\_2 \leq 200\\,000)$

출력

식당에 도착해 가장 오래 기다린 손님이 몇 시간을 기다렸는지 출력하라.

예제2

예제 1
입력
```
6
3 1
5 4
6 3
4 1
2 2
1 2
```
예상 출력
```
3
```
예제 2
입력
```
5
2 4
3 3
7 3
6 6
11 2
```
예상 출력
```
1
```