재접속 순번의 빈 구간

문제

게임 서버는 연결이 끊긴 이용자가 다시 접속할 때 사용할 재접속 순번을 기록한다. 순번은 0 이상 9999 이하의 정수다. 서버가 여러 기록 장치에서 자료를 모았으므로 기록의 순서는 뒤섞여 있으며, 같은 순번이 여러 번 나타날 수도 있다. 한 번이라도 기록에 나타난 순번은 사용 중인 것으로 취급한다. 같은 순번이 여러 번 나타나더라도 사용 중인 순번 하나로만 취급한다. 운영자는 임시 접속을 위한 순번을 확보하려 한다. 다만 현재 사용 범위 밖으로 순번을 확장할 수는 없다. 따라서 기록에 나타난 가장 작은 순번과 가장 큰 순번 사이에서만 빈 순번을 찾는다. 가장 작은 순번보다 작거나 가장 큰 순번보다 큰 순번은 기록에 없어도 후보가 아니다. 빈 구간은 이 범위 안에서 사용 중인 순번을 하나도 포함하지 않는 연속된 정수들의 구간이다. 구간의 시작 순번을 L, 끝 순번을 R이라고 하면 L부터 R까지의 모든 정수가 기록에 없어야 하며, 구간의 길이는 R-L+1이다. 순번 하나만 비어 있어도 길이가 1인 빈 구간이 된다. 기록이 입력된 위치나 같은 순번의 등장 횟수는 빈 구간의 길이에 영향을 주지 않는다. 운영자는 길이가 가장 긴 빈 구간 하나를 선택한다. 길이가 같은 빈 구간이 여러 개라면 시작 순번이 가장 작은 구간을 선택한다. 선택한 구간의 시작 순번과 끝 순번을 구하는 프로그램을 작성한다. 사용할 수 있는 빈 순번이 하나도 없다면 -1을 출력한다. 서로 다른 사용 중인 순번이 하나뿐인 경우에도 빈 구간은 없다.

입력

첫째 줄에 기록의 개수 N이 주어진다. N은 1 이상 70000 이하의 정수다.
둘째 줄에 각 기록의 재접속 순번 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 A_i는 0 이상 9999 이하의 정수이며, 같은 값이 여러 번 주어질 수 있다.

출력

길이가 가장 긴 빈 구간의 시작 순번과 끝 순번을 공백으로 구분하여 한 줄에 출력한다. 길이가 같은 구간이 여러 개라면 시작 순번이 가장 작은 구간을 출력한다. 빈 구간이 없다면 -1만 출력한다.

8
12 4 5 12 20 3 19 5

6 11

6
8 6 7 8 9 6

-1

3
9999 0 9999

1 9998

출처: Devin.KR 자체 제작