게임 서버의 첫 예약 충돌

문제

한 게임 서버는 특별 대전을 진행할 때 공용 경기 공간 하나를 사용한다. 백엔드 담당자는 다음 운영 구간에 등록된 예약들을 배포하기 전에, 같은 공간을 동시에 사용하도록 잡힌 시간이 있는지 검사하려 한다. 모든 예약은 같은 경기 공간을 대상으로 하며, 예약마다 사용 시작 시각과 사용 종료 시각이 정수로 기록되어 있다. 시각은 운영 구간의 기준점으로부터 지난 분을 나타낸다. 시작 시각이 s이고 종료 시각이 e인 예약은 s 이상 e 미만인 동안 공간을 사용한다. 즉, 시작 시각에는 이미 사용 중이지만 종료 시각에는 사용을 끝낸 상태이다. 따라서 한 예약이 끝나는 시각에 다른 예약이 시작하면 두 예약은 충돌하지 않는다. 시작 시각은 항상 종료 시각보다 작다. 서로 다른 예약 두 개 이상이 같은 시각에 공간을 사용하면 예약 충돌이 발생한다. 한 예약이 다른 예약의 사용 구간 전체를 포함하는 경우도 충돌이다. 시작과 종료 시각이 모두 같은 예약이 여러 개 등록되어 있다면 각각 별개의 예약이므로 서로 충돌한다. 입력에 적힌 예약 순서는 접수 순서일 뿐이며, 시간순으로 정렬되어 있다는 보장은 없다. 검사 프로그램은 충돌하는 예약의 번호나 모든 충돌 구간을 나열하지 않는다. 대신 전체 예약 중 처음으로 충돌이 발생하는 시각 하나만 보고한다. 모든 시작 및 종료 시각이 정수이므로 충돌이 존재하면 그 최초 시각도 정수이며, 어떤 예약의 시작 시각과 같다. 같은 시각에 여러 예약이 함께 충돌해도 그 시각은 한 번만 출력한다. 예약을 취소하거나 시간을 옮기는 작업은 수행하지 않는다. 주어진 예약을 모두 그대로 사용한다고 가정하여 최초 충돌 시각을 구한다. 운영 구간 전체에 걸쳐 동시에 사용되는 예약이 두 개 이상인 순간이 없다면 충돌이 없음을 나타내는 -1을 출력한다.

입력

첫째 줄에 예약 수인 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개 줄에 각 예약의 시작 시각 s와 종료 시각 e가 공백으로 주어진다. s와 e는 정수이며 0 ≤ s < e ≤ 99,999이다. 같은 예약 구간이 여러 번 주어질 수 있다.

출력

예약 충돌이 처음 발생하는 시각을 정수 하나로 출력한다. 충돌이 없으면 -1을 출력한다.

5
20 28
4 9
8 13
13 20
2 4

8

4
12 17
0 5
5 12
17 21

-1

3
7 11
7 11
1 7

7

출처: Devin.KR 자체 제작