연속 번호 묶음 호출

문제

한 은행은 영업을 시작한 뒤 방문 고객에게 1번부터 N번까지의 대기표를 차례대로 발급했다. 대기표 번호는 모두 서로 다르며, 발급된 번호 사이에 빠진 번호는 없다. 현재까지 일부 고객은 상담을 마쳤고, 나머지 고객은 대기 중이다. 상담을 마친 고객의 대기표 번호가 기록으로 주어진다. 은행은 추가 창구를 열면서 대기 중인 고객을 한 묶음으로 안내하려 한다. 안내할 묶음은 연속된 정수 번호로 이루어져야 한다. 즉, 두 정수 a와 b를 골랐을 때 a번부터 b번까지의 모든 고객이 아직 대기 중이어야 한다. 이미 상담을 마친 번호를 건너뛰어 두 구간을 하나로 합칠 수는 없다. 실제로 고객이 서 있는 위치나 상담을 마친 순서는 묶음을 정하는 데 영향을 주지 않는다. 은행은 한 번의 안내로 가장 많은 고객을 부르려고 한다. 따라서 만들 수 있는 묶음 중 포함된 번호의 개수가 가장 큰 묶음을 선택한다. 같은 개수의 고객을 포함하는 묶음이 여러 개라면 시작 번호가 가장 작은 묶음을 선택한다. 선택한 묶음의 시작 번호, 끝 번호, 고객 수를 구해야 한다. 예를 들어 어떤 번호가 상담 완료 기록에 없다면 그 번호의 고객은 반드시 대기 중인 것으로 처리한다. 기록에 나타난 번호는 모두 상담을 마친 것으로 처리하며, 같은 번호가 두 번 기록되지는 않는다. 상담을 마친 고객이 한 명도 없으면 발급한 모든 번호를 하나의 묶음으로 선택할 수 있다. 반대로 모든 고객이 상담을 마쳤다면 선택할 묶음이 없으므로 정해진 세 개의 0을 출력한다. 대기표의 총개수와 상담 완료 기록을 바탕으로 은행이 안내할 묶음을 결정하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 100,000이고 0 ≤ K ≤ min(N, 60,000)이다.
이후 K개의 줄에 상담을 마친 고객의 대기표 번호가 하나씩 주어진다. 각 번호는 1 이상 N 이하의 정수이며 서로 다르다. 번호가 주어지는 순서에는 제한이 없다. K가 0이면 이후 입력 줄은 없다.

출력

선택한 묶음의 시작 번호, 끝 번호, 고객 수를 공백으로 구분하여 한 줄에 출력한다. 고객 수가 같은 묶음이 여러 개라면 시작 번호가 가장 작은 것을 출력한다. 대기 중인 고객이 없으면 0 0 0을 출력한다.

12 4
9
3
8
4

5 7 3

8 2
6
3

1 2 2

3 3
2
1
3

0 0 0

출처: Devin.KR 자체 제작