환기 알림을 보낼 분

문제

스마트 홈 관리기는 매시간 한 번, 모든 방에 같은 시각으로 환기 알림을 보낸다. 알림 시각은 시 단위를 제외한 분으로 정하며, 선택할 수 있는 값은 0부터 59까지의 정수다. 관리기는 등록된 생활 기록을 참고하여 알림 때문에 방해받는 기록의 수가 가장 적은 분을 찾으려고 한다. 각 생활 기록에는 시작 분 S와 끝 분 E가 적혀 있다. 이 기록은 매시간 S분부터 E분까지 조용히 지내고 싶다는 뜻이다. 시작 분과 끝 분도 조용히 지내야 하는 시간에 포함된다. 따라서 알림을 보낸 분을 M이라고 할 때 S ≤ M ≤ E이면 그 기록은 방해받은 기록이 된다. 모든 기록은 한 시간 안에서 끝나며, 다음 시간으로 이어지는 구간은 주어지지 않는다. 관리기는 사람이나 방을 구분하지 않고 등록된 기록 한 줄을 하나의 요청으로 센다. 서로 같은 구간이 여러 번 등록되어 있어도 각각 별개의 기록이다. 한 알림 시각이 여러 구간에 포함되면 해당하는 기록을 모두 방해한 것으로 센다. 구간의 길이에 따른 추가 점수나 가중치는 없다. 예를 들어 8분부터 12분까지의 기록은 8분과 12분의 알림에도 방해받지만, 7분이나 13분의 알림에는 방해받지 않는다. 기록이 전혀 방해받지 않는 분이 있으면 그 분의 방해 기록 수는 0이다. 모든 분에서 하나 이상의 기록을 방해하더라도 알림을 생략할 수는 없다. 방해받는 기록 수가 가장 작은 분을 선택한다. 그러한 분이 여러 개이면 숫자가 가장 작은 분을 선택한다. 선택한 분과 그 분에 알림을 보냈을 때 방해받는 기록 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 생활 기록 수 N이 주어진다. N은 1 이상 5,000 이하의 정수다.
다음 N개 줄에 정수 S와 E가 공백으로 구분되어 주어진다. 각 줄은 하나의 기록이며 0 ≤ S ≤ E ≤ 59다. 같은 기록이 여러 번 주어질 수 있다.

출력

선택한 분과 방해받는 기록 수를 공백으로 구분하여 한 줄에 출력한다. 분은 앞에 0을 붙이지 않는 정수로 출력한다.

3
0 10
5 20
22 59

21 0

3
0 59
0 59
0 0

1 2

1
0 59

0 1

출처: Devin.KR 자체 제작