완전한 도로

면접 대비

시간 제한1초메모리 제한1024 MB

요약

구멍의 위치와 구간 길이 m이 주어졌을 때, 첫 구간의 시작 위치 k(1부터 m까지) 중 손상된 구간 수가 가장 적은 위치를 모두 찾고 그 최솟값을 구합니다.

난이도: 보통10점 중 5점
유형: 수학, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

우리의 아름다운 조국에서 도로는 시민들의 자랑이다. 특히 $A1$ 이라는 멋진 이름의 초고속도로가 그렇다. 안타깝게도 해마다 값싼 파테와 맥주 캔을 잔뜩 싣고 달리는 트라반트를 몬 많은 관광객이 도로를 망가뜨린다. 그래서 도로를 보수해야 한다.

국가 도로 완전성 연구소가 고속도로를 점검하고, 보수가 필요한 모든 구멍에 표시했다. 보수는 다음과 같이 진행된다. 먼저 첫 번째 손상보다 앞의 어떤 지점에서 시작해 도로를 같은 길이의 구간으로 나눈다. 그다음 손상이 있는 각 구간에 굴삭기 한 대와 작업팀을 보낸다.

국내에 굴삭기가 부족하므로, 교통 전문가가 손상이 있는 구간의 수가 최소가 되도록 주어진 길이의 구간으로 도로를 나누는 방법을 정해야 한다.

도로에는 $n$ 개의 구멍이 있으며, 각 구멍은 도로 시작점으로부터의 거리를 나타내는 정수로 주어진다. 각 구간의 길이는 자연수 $m$ 으로 정해져 있다. 도로의 처음 $m$ 미터에는 손상이 없다. 첫 번째 구간은 처음 $m$ 미터 중 한 지점에서 시작해야 한다. 첫 번째 구간이 $k$ 미터 지점에서 시작하면, $i$ 번째 구간은 $k + (i - 1) \cdot m$ 미터 지점에서 시작한다. 굴삭기 한 대는 어떤 구간의 시작점(포함)부터 다음 구간의 시작점(미포함)까지의 모든 구멍을 보수할 수 있다.

고속도로 보수에 필요한 굴삭기의 최소 개수와 첫 번째 구간이 시작할 수 있는 모든 위치를 구하는 프로그램을 작성하라.

입력

첫째 줄에 자연수 $m$ 과 $n$ 이 주어진다 ( $1 \le m, n \le 100\,000$ ).

둘째 줄에는 모든 구멍의 위치 $x_1, x_2, \dots, x_n$ 이 주어진다 ( $m < x_1 < x_2 < \dots < x_n \le 2 \cdot 10^9$ ).

출력

첫째 줄에 고속도로 보수에 필요한 굴삭기의 최소 개수를 출력한다.

둘째 줄에는 첫 번째 구간이 시작할 수 있는 모든 위치를 오름차순으로 출력한다. 각 수는 공백 한 칸으로 구분한다.

예제3

예제 1
입력
```
3 5
4 5 7 8 9
```
예상 출력
```
2
1
```
예제 2
입력
```
4 3
7 14 15
```
예상 출력
```
2
1 2 4
```
예제 3
입력
```
2 10
3 4 7 8 12 13 14 15 20 21
```
예상 출력
```
7
1 2
```