소몰이 timer 1s memory - MB

농부 창호는 헛간에 데리고 있던 n(1≤n≤5,000)마리의 소들을 한 줄로 세워놓았다.

대부분의 (착한) 소들은 앞을 보고 있다. 하지만 농부 창호는 뒤를 보고 있는 몇몇 (나쁜) 소들을 앞을 향하도록 만들어야 한다.

다행히도 농부 창호는 최근에 자동으로 소들의 위치를 뒤집어 버리는 기계를 샀다. 하지만 농부 창호는 너무나 짠돌이 습성이 발휘 되어 돈을 아끼는 바람에 기계는 몇 가지 기능이 제한되어 있다.

첫째로, 일단 k(1≤k≤n)를 설정하고 나면 한 번에 소를 더도 덜도 아닌 정확히 k마리씩 뒤집어야 한다. 둘째로, 소를 뒤집을 때는 반드시 연속된 k마리의 소를 뒤집어야 한다. 중요한 것은 소들은 위치의 이동 없이 그 장소에서 방향을 뒤집는다는 것이다.

기계를 사용하는 것은 정말 귀찮은 일이기 때문에, 농부 창호는 기계를 최소로 사용하도록 하는 k를 선택하려고 한다(만약 그러한 k가 여러 개 있다면 가장 작은 k를 선택하려고 한다). 농부 창호를 도와서 기계사용 횟수를 최소로 하는 k와, 그 최소 사용 횟수 m을 출력하자.