사회적 거리두기 1 timer 1s memory 128MB

농부 창호는 무시무시한 소로나 바이러스(COWVID-19)로부터 자신의 소들을 보호하고자 한다.

소들이 살고 있는 공간은 왼쪽 끝 0번 헛간부터 N-1번 헛간까지 차례대로 배치된 N개의 헛간으로 나누어져 있다.

이 중에는 이미 소가 거주하고 있는 곳도 있고 없는 곳도 있다.

소 두 마리가 최근에 무리에 합류해서, 새로운 헛간을 배정받아야 한다. (이미 살고 있던 소들의 거주지는 옮기지 않는다.)

각 거주지간의 거리 중 가장 가까운 거리를 D라고 하자.

농부 창호는 소로나 바이러스 예방을 위해, 두 마리의 소에게 거주지를 배정한 후의 D를 최대화시키려고 한다.

D의 최대값을 구하는 프로그램을 작성하라.