A1
시간 제한1초메모리 제한128 MB
고속도로를 길이 M 구간으로 나눌 때 손상 지점을 포함하는 구간 수가 최소가 되는 시작 위치 K(1부터 M까지)를 모두 구하는 문제입니다.
문제
어떤 나라에는 A1이라는 주요 고속도로가 있다. 이 도로에는 알려진 파손 지점들이 있고, 수리팀은 같은 길이의 도로 구간마다 배정된다. 파손 지점 수에 비해 수리팀이 부족할 수 있으므로, 파손을 포함하는 구간의 수가 최소가 되도록 첫 구간의 시작 위치를 정해야 한다.
알려진 파손 지점은 N개이며, 각 지점은 고속도로 시작점으로부터의 거리(미터)를 나타내는 정수로 주어진다. 각 구간의 길이는 M미터이다. 고속도로의 처음 M미터 안에는 파손 지점이 없다.
첫 구간은 정수 위치 1부터 M까지 중 하나에서 시작해야 한다. 첫 구간이 K번째 미터에서 시작한다면, L번째 구간은 K + (L - 1) * M번째 미터에서 시작한다. 한 구간에 배정된 수리팀은 그 구간의 첫 미터부터 마지막 미터까지에 있는 모든 파손을 수리할 수 있다.
A1 고속도로의 모든 파손을 수리하는 데 필요한 수리팀 수의 최솟값과, 그 최솟값을 만들 수 있는 첫 구간의 시작 위치 K를 모두 구하라.
입력
첫째 줄에 두 정수 M과 N이 공백으로 구분되어 주어진다. 1 <= M, N <= 100000이며, M은 한 구간의 길이, N은 파손 지점의 개수이다.
둘째 줄에는 모든 파손 지점의 위치를 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 각 위치는 M보다 크고 2000000000 이하이다. 주어지는 위치들은 항상 엄격히 증가한다.
출력
첫째 줄에 필요한 수리팀 수의 최솟값을 출력한다.
둘째 줄에 그 최솟값을 만들 수 있는 첫 구간의 시작 위치를 모두 출력한다. 수들은 공백으로 구분해야 하며, 엄격히 증가하는 순서여야 한다.