Valsts galvenā šoseja ir "A1" un tās uzturēšanai kārtībā tiek pievērsta pastiprināta uzmanība. Katru pavasari tiek noskaidroti ziemā radušies bojājumi un to novēršanai tiek izsūtītas bojājumu novēršanas brigādes.
Ir zināms, ka pirmajos M šosejas metros bojājumu nav. Visa šoseja tiek sadalīta M metrus garos posmos tā, ka pirmais posms sākas K-tajā metrā (1 ≤K≤M) un šie posmi seko viens otram bez atstarpēm. Tāpēc, piemēram, L-tais posms sākas šosejas (K+(L-1)*M)-tajā metrā.
Katra bojājumu novēršanas brigāde var apkalpot tieši vienu šādu posmu, neatkarīgi no tā, cik bojājumu tajā ir. Protams, ja kādā posmā bojājumu nav, tad brigāde turp nav jāsūta.
Uzrakstiet programmu, kas nosaka, kāds mazākais bojājumu novēršanas brigāžu skaits ir nepieciešamas un kuros šosejas metros šajā gadījumā vajag sākt šosejas dalījumu posmos!
Teksta faila a1.dat pirmajā rindā dotas divu naturālu skaitļu M (posma garums) un N (bojājumu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 1≤M,N≤100000.
Faila otrajā rindā doti N naturāli skaitļi, kas atdalīti ar tukšumsimboliem - bojāto šosejas metru numuri augošā secībā (pirmais šosejas metrs tiek apzīmēts ar 1, otrais ar 2, utt.). Katrs no skaitļiem ir lielāks par M un nepārsniedz 2*109.
Teksta faila a1.rez pirmajā rindā jāizvada mazākais nepieciešamais bojājumu novēršanas brigāžu skaits. Faila otrajā rindā jāizvada visu to šosejas metru numuri augošā secībā, kur var sākties šosejas dalījums posmos, lai nepieciešamais brigāžu skaits būtu vismazākais.
| a1.dat | a1.rez |
3 5 4 5 7 8 9 |
2 1 |
| a1.dat | a1.rez |
4 3 7 14 15 |
2 1 2 4 |
| a1.dat | a1.rez |
2 10 3 4 7 8 12 13 14 15 20 21 |
7 1 2 |