예약표의 가장 긴 빈 구간

문제

한 병원은 하루의 진료 시간을 길이가 같은 N개의 예약 칸으로 나누어 관리한다. 예약 칸에는 시간 순서대로 1부터 N까지 번호가 붙어 있다. 서로 이웃한 번호의 칸은 시간상으로도 바로 이어진다. 하루의 마지막 칸과 첫 번째 칸은 이어져 있지 않다. 병원은 현재 예약표에서 가장 길게 이어지는 빈 구간을 찾아 내부 점검 시간을 배정하려 한다. 예약 시스템에는 M개의 예약 알림이 도착했다. 각 알림에는 예약된 칸의 번호가 하나 적혀 있다. 알림이 시간 순서대로 도착한다는 보장은 없으며, 같은 예약에 대한 알림이 여러 번 도착할 수도 있다. 같은 번호가 여러 번 주어져도 그 칸 하나만 예약된 것으로 처리한다. 알림에 한 번도 등장하지 않은 칸은 비어 있다. 예약 취소를 나타내는 알림은 없다. 빈 구간은 시작 번호 L부터 끝 번호 R까지의 모든 칸이 비어 있는 구간을 뜻한다. L과 R은 정수이며 1 ≤ L ≤ R ≤ N이다. 이 구간의 길이는 R-L+1이다. 구간 내부에 예약된 칸이 하나라도 있으면 빈 구간으로 선택할 수 없다. 서로 떨어져 있는 빈 칸들을 합쳐 하나의 구간으로 취급할 수도 없다. 병원은 길이가 가장 긴 빈 구간 하나를 선택한다. 가장 긴 빈 구간이 여러 개라면 시작 번호 L이 가장 작은 구간을 선택한다. 길이가 같고 시작 번호도 같다면 끝 번호도 같으므로 추가적인 동점 규칙은 필요하지 않다. 선택한 구간의 시작 번호와 끝 번호를 출력해야 한다. 예약된 칸이 하나도 없다면 하루 전체가 하나의 빈 구간이 된다. 반대로 모든 칸이 예약되어 빈 구간을 만들 수 없다면 정해진 표시인 0 0을 출력한다. 예약 알림 목록을 바탕으로 점검 시간으로 선택할 구간을 구하는 프로그램을 작성하라.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000이고 0 ≤ M ≤ 40,000이다.
다음 M개 줄에 예약 알림의 칸 번호 X_i가 하나씩 주어진다. X_i는 정수이며 1 ≤ X_i ≤ N이다. 같은 번호가 여러 번 주어질 수 있다.
M이 0이면 예약 알림을 나타내는 줄은 주어지지 않는다.

출력

선택한 빈 구간의 시작 번호 L과 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 빈 구간이 없으면 0 0을 출력한다.

10 5
4
8
4
9
10

1 3

3 3
2
1
3

0 0

6 0

1 6

출처: Devin.KR 자체 제작