Buggy python submission (verdict: Runtime Error):
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            while l+mid <= S[i+1] and cnt <= m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Fixed submission:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = 0; right = sum(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt<=m and l<=target:
                l += mid-(S[i]-l)
                cnt += 1
            if (l+mid <= S[i+1] or abs(l-S[i]) < abs(l-S[i+1])) and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
                if l+mid <= S[i+1]:
                    cnt += S[i+1]-mid+1-l
                    l = S[i+1]-mid+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m-1 <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print left

Buggy python submission (verdict: Runtime Error):
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            assert S[i]<l+mid
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            if l+mid <= S[i+1] and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1

                if l <= S[i+1]-mid and l<=target:
                    cnt += min(S[i+1]-mid,target)-l+1
                    l = min(S[i+1]-mid,target)+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Fixed submission:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = 0; right = sum(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt<=m and l<=target:
                l += mid-(S[i]-l)
                cnt += 1
            if (l+mid <= S[i+1] or abs(l-S[i]) < abs(l-S[i+1])) and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
                if l+mid <= S[i+1]:
                    cnt += S[i+1]-mid+1-l
                    l = S[i+1]-mid+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m-1 <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print left