고속도로 보수 구간 나누기

바이타자르(Bajtazar)는 직사각형 판에 블록을 쌓는 기술을 완벽히 익혔고, 뛰어난 손재주 덕분에 빠르게 승진하여 인프라부(Ministry of Infrastructure)에 들어갔다. 그의 임무는 건설 인부들의 작업을 최적화하는 것이며, 지금은 고속도로 A1의 보수를 맡고 있다.

고속도로의 킬로미터에는 $1, 2, 3, \dots$ 순서로 번호가 매겨져 있다. 고속도로는 길이가 $m$킬로미터인 여러 구간으로 나뉜다. 첫 번째 구간이 $s$번째 킬로미터에서 시작한다면, $t$번째 구간은 $s + (t-1)\,m$번째 킬로미터에서 시작한다. 즉 $t$번째 구간은 킬로미터 $s+(t-1)m$부터 $s+t\,m-1$까지를 덮는다.

고속도로의 각 킬로미터에 대해 보수가 필요한지 여부가 주어진다. 보수가 필요한 킬로미터를 하나 이상 포함하는 모든 $m$킬로미터 구간에는 건설 인부 팀을 한 팀씩 보내야 한다. 파견하는 팀의 수가 최소가 되도록 고속도로를 구간으로 나누는 것이 목표이다.

첫 번째 구간은 반드시 처음 $m$개의 킬로미터 중 하나에서 시작해야 한다. 즉 $s$는 $1 \le s \le m$을 만족한다. 또한 고속도로의 처음 $m$개 킬로미터는 어느 것도 보수가 필요하지 않다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 고속도로의 손상 정보를 읽는다.
• 필요한 건설 팀 수를 최소로 만드는 구간 분할을 구한다.
• 결과를 표준 출력에 출력한다.

첫째 줄에 두 정수 $m$과 $u$가 주어진다 ($1 \le m, u \le 100000$). $m$은 한 구간의 길이이고, $u$는 보수가 필요한 킬로미터의 개수이다.

둘째 줄에는 증가하는 순서로 정렬된 정수 $a_i$가 $u$개, 공백 하나로 구분되어 주어진다 ($0 \le a_i \le 2000000000$). 각 $a_i$는 보수가 필요한 킬로미터 하나를 나타낸다.

첫째 줄에 파견되는 건설 팀의 최소 개수를 출력한다.

둘째 줄에는 첫 번째 구간이 시작될 수 있는 모든 위치, 즉 팀 수를 최소로 만드는 모든 시작 킬로미터 $s$를 증가하는 순서로 공백으로 구분하여 출력한다.