[백준] 2110번 : 공유기 설치 with python3

N, C = map(int, input().split())
routers = [int(input()) for _ in range(N)]
routers.sort()

def possible(a, c, mid):
    cnt = 1
    last = a[0]
    for house in a:
        if house - last >= mid :
            # 거리가 mid보다 크면
            cnt += 1
            # 되는 수를 늘린다.
            last = house
            # last에 매번 house를 넣는다.
            # 왜냐면 각 house마다의 거리를 넣어야하니까
    return cnt >= c
    # 수가 c보다 높으면


ans = 1
l = 1
r = routers[N-1] - routers[0]


while l <= r:
    mid = (l+r)//2
    if possible(routers, C, mid):
        ans = max(ans,mid)
        l = mid+1
    else:
        r = mid-1

print(ans)