In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.
Rick stated that magnetic force between two different balls at positions x and y is |x - y|.
Given the integer array position and the integer m. Return the required force.
 
Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:
Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

 
Constraints:

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
All integers in position are distinct.
2 <= m <= position.length

Difficulty: interview

Starter code:

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        

Solutions:
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        max_distance_between = (position[-1] - 1) // (m - 1)
        min_distance_between = 1
        
        if self.isDistancePossible(max_distance_between, position, m): return max_distance_between
        
        while max_distance_between > min_distance_between + 1:
            middle_distance = (min_distance_between + max_distance_between) // 2
            
            if self.isDistancePossible(middle_distance, position, m):
                min_distance_between = middle_distance
            else:
                max_distance_between = middle_distance
                
        return min_distance_between
    
    def isDistancePossible(self, distance, position, m):
        used_ball_count = 0
        previous_used_position = float('-inf')
        
        for pos in position:
            if pos - previous_used_position >= distance:
                used_ball_count += 1
                previous_used_position = pos
                
        return used_ball_count >= m

class Solution:
    def maxDistance(self, p: List[int], m: int) -> int:
        
        def isvalid(f: int):            
            buckets, pos = 1, p[0]           
            for x in p:
                if f <= x - pos:
                    buckets += 1
                    if buckets == m:  return True
                    pos = x            
            return False
        
        p.sort()        
        lb, ub = 1, (p[-1] - p[0]) // (m - 1) + 1
        
        while 1 < ub - lb:
            
            f = (lb + ub) // 2
            
            if isvalid(f): lb = f  
            else: ub = f
            
        return lb


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        res = -1
        if m == 2:
            return position[-1]-position[0]
        
        def count(spacing):
            count = 1
            prev_pos = position[0]
            for pos in position:
                if pos-prev_pos>=spacing:
                    count+=1
                    prev_pos = pos
            return count
        
        
        left,right = 1,math.ceil(position[-1]/(m-1))
        while left<=right:
            mid = (left+right)//2
            if count(mid)>=m:
                res = mid
                left = mid+1
            else:
                right = mid-1
        
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        sorted_position = sorted(position)
        
        N = len(position)
        lo = 1
        hi = sorted_position[N-1] - sorted_position[0]
        
        last_achieved = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if self._try_target(mid, sorted_position, m):
                lo = mid+1
                last_achieved = mid
            else:
                hi = mid-1
        
        return last_achieved
    
    def _try_target(self, target: int, positions: List[int], m:int) -> bool:
        slotted = 1
        last_slotted = positions[0]
        
        for i in range(1, len(positions)):
            if positions[i] - last_slotted >= target:
                slotted += 1
                last_slotted = positions[i]
        
        return slotted >= m


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        @lru_cache(maxsize=None)
        def dfs(i, k, i0):
            # put k balls into position[i:] with max min force
            # i0 is the position with the largest index between position[0] and position[i-1]
            # d0 is the max min force between balls placed between position[0] and position[i-1]
            if k > (n-i):
                return 0
            if k == 1:
                return position[n-1]-position[i0]
            if k == 0:
                return 1e20

            d = 0
            for j in range(i, n):
                d_new = dfs(j+1, k-1, j)
                d = max(min(d_new, position[j]-position[i0]), d)
                        
            return d
        
        #return dfs(1, m-1, 0)
            
        @lru_cache(None)
        def f(i, k):
            if k == 0:
                return float('inf')
            if i == len(position):
                return float('-inf')
               
            ret = f(i+1, k)
            for x in range(i+1, len(position)):
                v = min(position[x] - position[i], f(x, k-1))
                ret = max(ret, v)
            
            return ret
        
        #return f(0, m-1)

        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
    
    # position = [1,2,3,4,7], m = 3, n=5
    # dfs(0, 3, -1e20, 1e20)
    # i=0, k=3, n-i=5
    # j=0, d0_new = 1e20, 
    # dfs(1, 2, 0, 1e20): d_new = ?
    # dfs(2, 2, 1, 1e20): d_new = ?
    # dfs(3, 2, 2, 1e20): d_new = 
    # dfs(4, 2, 3, 1e20): k=2 > 5-4=1, d_new = 0


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        res = 0
        
        def count(d):
            cur, ans = position[0], 1
            for i in range(1, n):
                if position[i] - cur >= d:
                    ans += 1
                    cur = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        return self.binaryS(0, position[-1], position, m)
    

    def binaryS(self, left, right, position, m):
        while left < right:
            mid = (left + right) // 2
            val = self.check(position, mid + 1, m)
            if val: left = mid + 1
            else: right = mid
        return right
                
        
        
    def check(self, position, interval, m) -> bool:
        total = 1
        start = position[0]
        for i in range(1, len(position)):
            if position[i] - start  >= interval:
                total += 1
                start = position[i]
        return total >= m

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def isPossible(x):
            count = m-1
            curr = position[0]
            for i in range(1,n):
                if position[i]-curr>=x:
                    count-=1
                    curr = position[i]
                if not count:
                    return True
            return False
        
        n = len(position)
        position.sort()
        lo = 1
        hi = position[-1]-position[0]+1
        
        while hi-lo>1:
            mid = lo + (hi-lo)//2
            
            if isPossible(mid):
                lo = mid
            else:
                hi = mid
        
        return lo

import numpy as np

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # Choose m values from n such that the minimum of the differences is maximized
        position.sort()
        
        def check(check_val):
            temp_m = m-1
            
            previous_pos = position[0]
            
            for p in position[1:]:
                if p - previous_pos >= check_val:
                    previous_pos = p
                    temp_m -= 1
                    if temp_m == 0:
                        return True
            return False
        
        l = 0   # min return value
        r = (position[-1] - position[0]) # max return value
        
        ret = l
        while l <= r:
            val = (l+r)//2
            if check(val):
                ret = max(ret, val)
                l = val + 1
            else:
                r = val-1
        return ret
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        return self.binaryS(0, position[-1], position, m)
    

    def binaryS(self, left, right, position, m):
        while left < right:
            mid = (left + right) // 2
            val = self.check(position, mid + 1, m)
            if val: left = mid + 1
            else: right = mid
        return left
                
        
        
    def check(self, position, interval, m) -> bool:
        total = 1
        start = position[0]
        for i in range(1, len(position)):
            if position[i] - start  >= interval:
                total += 1
                start = position[i]
        return total >= m

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        n = len(A)
        A.sort()
        
        def count(d):
            ans, curr = 1, A[0]
            for i in range(1, n):
                if A[i] - curr >= d:
                    ans += 1
                    curr = A[i]
            return ans
        
        l, r = 0, A[-1] - A[0]
        while l < r:
            mid = (l+r+1) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l <= r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid + 1
            else:
                r = mid - 1
        return r


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def helper(distance):
            balls = m - 1
            previous = position[0]
            for i in position[1:]:
                if i - previous >= distance:
                    balls -= 1
                    if balls == 0:
                        return True
                    previous = i
            return False
            
        position.sort()
        min_distance = 1
        max_distance = (position[-1] - position[0]) // (m - 1)
        # max_distance = position[-1] - position[0]
        result = 1
        while min_distance <= max_distance:
            mid = (min_distance + max_distance) // 2
            if helper(mid):
                result = mid
                min_distance = mid + 1
            else:
                max_distance = mid - 1
        return result

import bisect
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def is_ok(x):
            cur = -x
            for i in range(m):
                j = bisect.bisect_left(position, cur+x)
                if 0 <= j < len(position):
                    cur = position[j]
                else:
                    return False
            else:
                return True
                    
            
        l = 0
        r = 10**18
        while l+1 < r:
            c = (l+r)//2
            if is_ok(c):
                l = c
            else:
                r = c
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

import math
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        max_possible_answer = (position[-1] - position[0]) // (m-1) #3
        
        # linear search - time limit exceed
        # for i in range(1,1+max_possible_answer): 
        #     if not self.is_possible( position, m, i):
        #         break
        # return i-1

        # binary search
        l = 1
        r = max_possible_answer + 1 
        # T T T T T F F -> want to know last T
        # similar to 278
        while l < r :
            # why + 1?? because we use l = mid (inclusive) if we don't round up 
            # it will get stuck
            # mid = (r+l) // 2  + 1
            mid = math.ceil((r+l)/2)
            if self.is_possible( position, m, mid):
                l = mid # mid may be answer
            else:
                r = mid-1 # mid can't be answer
        return l
        
    def is_possible(self, position, m, gap):
        i = 1
        prev = position[0]
        m -= 1
        while i < len(position) and m > 0:
            if position[i] - prev >= gap:
                m -= 1
                prev = position[i]
            else:
                i += 1

        return m == 0


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = (r+l+1) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def getBallCount(position, force):
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        # position.sort()
        # l,r,ans=0,position[-1],0
        # while l<=r:
        #     gap=l+(r-l)//2
        #     if getBallCount(position, gap) >= m:
        #         ans=gap
        #         l=gap+1
        #     else:
        #         r=gap-1
        # return ans
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                res = mid
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        left = 0
        right = position[-1] - position[0]
        
        best = 0
        while left <= right:
            target = left + (right-left)//2
            if self.solve(position, m, target):
                left = target+1
                best = max(best, target)
            else:
                right = target-1
        
        return best

    
    def solve(self, position, m, target):
        p = position[0]
        m -= 1
        
        for p2 in position[1:]:
            if p2 - p >= target:
                m -= 1
                p = p2
            
            if m == 0:
                return True
        
        return False


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l = 0
        r = (position[-1]-1) // (m-1) * 2
        while l < r:
            intrv = (l+r) // 2
            c = 0
            prev = float('-inf')
            for p in position:
                if p >= prev + intrv:
                    c += 1
                    prev = p
            if c >= m:
                best = intrv
                l = intrv + 1
            else:
                r = intrv
        return best


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        max_possible_answer = (position[-1] - position[0]) // (m-1) #3
        
        # linear search - time limit exceed
        # for i in range(1,1+max_possible_answer): 
        #     if not self.is_possible( position, m, i):
        #         break
        # return i-1

        # binary search
        l = 1
        r = max_possible_answer + 1 
        # T T T T T F F -> want to know last T
        # similar to 278
        while l < r :
            # why + 1?? because we use l = mid (inclusive) if we don't round up 
            # it will get stuck
            mid = (r+l) // 2  + 1
            if self.is_possible( position, m, mid):
                l = mid # mid may be answer
            else:
                r = mid-1 # mid can't be answer
        return l
        
    def is_possible(self, position, m, gap):
        i = 1
        prev = position[0]
        m -= 1
        while i < len(position) and m > 0:
            if position[i] - prev >= gap:
                m -= 1
                prev = position[i]
            else:
                i += 1

        return m == 0


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(position,val,m):
            balls = 1
            prev = position[0]
            for i in range(1,len(position)):
                if (position[i]-prev) >= val:
                    prev = position[i]
                    balls += 1
            if balls >= m:
                return True
            return False
        
        position.sort()
        lo,hi = 0 , position[-1]-position[0]
        while lo < hi:
            mid = (hi+lo+1)//2
            if check(position,mid,m):
                lo = mid
            else:
                hi = mid-1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left, right = 1, position[-1] - position[0]
        while left <= right:
            mid = left + (right - left)//2
            num_balls = self.count(position, m, mid)
            if num_balls > m:  # too many balls can fit in the given baskets, force is too small, search the right hal
                left = mid + 1
            elif num_balls == m:  # need to find the maximum force, continue to search the right half
                left = mid + 1
            else:
                right = mid -1
        return left -1

    def count(self, position, m, mid):
        prev = position[0]
        m =1
        for i in position[1:]:
            # if i - mid == prev:
            if i - prev >=mid:
                m+=1
                prev = i
        return m


class Solution:
    # https://leetcode.com/problems/magnetic-force-between-two-balls/discuss/803580/Python-Solution-or-Binary-Search
    def maxDistance(self, position: List[int], m: int) -> int:
        def getBallCount(position, force):
            # res starts from 1, since we put one ball at index = 0.
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                res = mid
            else:
                r = mid
        # return res, not l.
        return res

import bisect
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        def possible(gap):
            prev = position[0]
            idx = 0
            left = m - 1
            while left > 0:
                idx = bisect.bisect_left(position, prev+gap, idx + 1, n)
                if idx >= n:
                    return False
                else:
                    prev = position[idx]
                    left -= 1
            return True
        
        position.sort()
        min_gap = 1
        max_gap = position[-1] - position[0]
        while min_gap < max_gap:
            cur_gap = (min_gap + max_gap + 1) // 2
            
            prev = position[0]
            idx = 0
            left = m - 1
            res = True
            while left > 0:
                idx = bisect.bisect_left(position, prev + cur_gap, idx + 1, n)
                if idx >= n:
                    res = False
                    break
                else:
                    prev = position[idx]
                    left -= 1
            
            if res:
                min_gap = cur_gap
            else:
                max_gap = cur_gap - 1
                
        return min_gap

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def helper(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        left, right = 0, position[-1] - position[0]
        while left <= right:
            mid = left + (right - left) // 2
            if helper(mid) < m:
                right = mid - 1
            else:
                left = mid + 1
        
        return left - 1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def getBallCount(position, force):
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        # position.sort()
        # l,r,ans=0,position[-1],0
        # while l<=r:
        #     gap=l+(r-l)//2
        #     if getBallCount(position, gap) >= m:
        #         ans=gap
        #         l=gap+1
        #     else:
        #         r=gap-1
        # return ans
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                res = mid
            else:
                r = mid
        # return res, not l.
        return res

class Solution:
    # https://leetcode.com/problems/magnetic-force-between-two-balls/discuss/803580/Python-Solution-or-Binary-Search
    def maxDistance(self, position: List[int], m: int) -> int:
        def getBallCount(position, force):
            # res starts from 1, since we put one ball at index = 0.
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                # record res 
                res = mid
            else:
                r = mid
        # return res, not l.
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev >= force:  
                
                    prev= x
                    balls_placed+=1  
                
            return(balls_placed>=m)
        
        lo,hi = 0, max(position)
        while lo<hi:
            mid = (lo+hi+1)//2
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def valid(position, force):
            prev, j = 0, 1
            for i in range(1, m):
                while j < len(position) and position[j] - position[prev] < force:
                    j += 1
                if j == len(position):
                    return False
                prev = j
            return True
        
        def getBallCount(position, force):
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        # position.sort()
        # l,r,ans=0,position[-1],0
        # while l<=r:
        #     gap=l+(r-l)//2
        #     if getBallCount(position, gap) >= m:
        #         ans=gap
        #         l=gap+1
        #     else:
        #         r=gap-1
        # return ans
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                res = mid
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        
        def is_valid(guess):
            prev = position[0]
            balls = 1
            for p in position[1:]:
                if p-prev >= guess:
                    prev = p
                    balls += 1
                if balls == m:  
                    return True
            return False
                    
        l, r = 1, (position[-1]-position[0]) // (m-1)
        while l < r:
            guess = (l + r + 1) >> 1 
            if is_valid(guess):
                l = guess
            else:    
                r = guess-1
        return l        
        


    #    position.sort()
    #    l, r = 1, position[-1] - position[0]
    #    while l < r:
    #        cand = (l + r + 1) >> 1
    #        if self.is_valid(position, m, cand):
    #            l = cand
    #        else:    
    #            r = cand - 1
    #    return l        
    #
    #def is_valid(self, position, m, cand):
    #    prev = position[0]
    #    rem = m - 1
    #    for pos in position[1:]: 
    #        if pos >= prev + cand:
    #            prev = pos
    #            rem -= 1
    #        if rem == 0:    
    #            return True
    #    return False


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        l, r = 0, position[n-1]-position[0]
        while l < r:
            mid = (r + l + 1) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    # https://leetcode.com/problems/magnetic-force-between-two-balls/discuss/803580/Python-Solution-or-Binary-Search
    def maxDistance(self, position: List[int], m: int) -> int:
        def getBallCount(position, force):
            res, prev = 1, 0
            for i in range(1, len(position)):
                if position[i] - position[prev] >= force:
                    res += 1
                    prev = i
            return res
        
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        l, r, res = 0, position[-1] + 1, 0
        while l < r:
            mid = l + (r - l) // 2
            # force is too small
            if getBallCount(position, mid) >= m:
                l = mid + 1
                res = mid
            else:
                r = mid
        # return res, not l.
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        if len(position) < m:
            return 0
        
        def valid_force(f):
            ball_pos = 0
            balls = m - 1
            for i in range(1, len(position)):
                if position[i] - position[ball_pos] >= f:
                    balls -= 1
                    ball_pos = i
                    if balls == 0:
                        return True
            
            return False
        
        position.sort()
        l, h = 1, position[-1]
        while l < h:
            f = l + (h - l + 1) // 2
            if valid_force(f):
                l = f
            else:
                h = f - 1
        
        return l
            


class Solution:
    def is_force_valid(self, position: List[int], m: int, force: int) -> bool:
        last_pos = position[0]
        m -= 1
        for i in range(1, len(position)):
            if position[i] - last_pos >= force:
                m -= 1
                if m == 0:
                    return True
                last_pos = position[i]
        return False
        
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left = 1
        right = position[-1] - position[0]
        

        while right > left:
            mid = (right + left + 1) // 2
            if self.is_force_valid(position, m, mid):
                left = mid
            else:
                right = mid - 1

        return left
    


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
#         def pd(i, m):
#             if m == 1:
#                 return float(\"inf\")
            
#             if memo[i][m]:
#                 return memo[i][m]
            
#             res = 0
            
#             for j in range(i+1, len(position)):
#                 res = max(res, min(position[j] - position[i], pd(j, m-1)))
                
#             memo[i][m] = res
            
#             return res
        
#         position = sorted(position)
        
#         memo = [(1 + m) * [0] for _ in range(1 + len(position))]
        
#         res = pd(0, m)
    
        position = sorted(position)
        
        if m == 2:
            return position[-1] - position[0]
        
        def solve(threshold, m):
            last_ball_pos = position[0]
            
            for pos in position[1:]:
                if pos - last_ball_pos >= threshold:
                    m -= 1
                    last_ball_pos = pos
                
                if m == 0:
                    return True
                
            return False
        
        start = 0
        end = position[-1] - position[0]
        
        res = 0
        
        while start <= end:
            middle = (start + end) // 2
                
            if solve(middle, m-1):
                start = middle + 1
                res = max(res, middle)
                
            else:
                end = middle - 1
    
        return res

class Solution:
    def maxDistance(self, position, m):
        position = sorted(position)
        start, end = 1, position[-1] - position[0]
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.check(position, m, mid):
                start = mid
            else:
                end = mid
        if self.check(position, m, end):
            return end
        if self.check(position, m, start):
            return start
    
    def check(self, position, m, delta):
        n = len(position)
        i = 1
        last = position[0]
        for j in range(1, n):
            if position[j] >= last + delta:
                last = position[j]
                i += 1
                if i == m:
                    return True
        return i == m

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev >= force:  # then that means we have that required force and we can keep a new ball here at position x
                    prev= x
                    balls_placed+=1
                    
                if balls_placed ==m: # if at any moment we are able to place m balls, we stop and return True.
                    return(True)     
            return(False)
        
        lo,hi = 0, max(position)
        while lo<hi:
            mid = (lo+hi+1)//2
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(x: int):
            pre = position[0]
            num = 1
            for ii in range(1, N):
                if position[ii] - pre >= x:
                    pre = position[ii]
                    num += 1
            return num >= m
            
        N = len(position)
        position = sorted(position)
        left, right, res = 0, position[-1] - position[0], -1
        while left <= right:
            mid = (left + right) >> 1
            if check(mid):
                res = mid
                left = mid + 1
            else:
                right = mid - 1
        return res


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        s = 1 
        e = (position[-1]-position[0]) // max(m-1, 1) + 1
        
        def check(mid) :
            t = position[0]
            ret_val = 1
            for k in position :
                if ret_val == m :
                    return True
                if k - t >= mid :
                    ret_val += 1
                    t = k
            return ret_val == m
        
        while e > s + 1 :
            mid = (e+s)//2
            if check(mid) :
                s = mid
            else :
                e = mid
        return s
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        length = len(position)
        position.sort()

        def count(d):
            minmax = 1
            curr = position[0]
            for i in range(1, length):
                if position[i] - curr >= d:
                    minmax += 1
                    curr = position[i]
            return minmax

        lo, hi = 0, position[-1] - position[0]
        while lo < hi:
            mid = hi - (hi - lo) // 2
            if count(mid) >= m:
                lo = mid
            else:
                hi = mid - 1
        return lo
    


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # sort balls
        position.sort()
        # number of balls that can be placed while the difference of two balls is at least diff
        def count_balls(diff):
            nballs, cur = 1, position[0]
            for i in range(1, len(position)):
                if position[i] - cur >= diff:
                    nballs += 1
                    cur = position[i]
            return nballs
        # m can range from 1 to position[-1] - position[0]
        # try out values of m using binary search on left and right
        left, right = 1, position[-1] - position[0]
        while left <= right:
            mid = (left + right) // 2
            if count_balls(mid) >= m:
                left = mid + 1
            else:
                right = mid - 1
                
        return right


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    curr, ans = position[i], ans + 1
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
    def maxDistancwe(self, position: List[int], m: int) -> int:
        def count(mid):
            r, c = 1, position[0]
            for i in range(1,len(position)):
                if position[i]-c >= mid:
                    c, r = position[i], r + 1
            return r
        position.sort()
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = (r + l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def isfail(mid):
            ans = 1
            curr = position[0] # alike greedy idea, we just put the first ball at position 0!
            for i in range(1, n):
                if position[i] - curr >= mid:
                    ans += 1
                    curr = position[i]
            return ans < m
        
        left = 0 # 注意，不应该把left赋值为min(position)! 因为我们求得是distance!
        # note that, left = min(position) is wrong, since we are looking for 'distance'!
        right = max(position) - min(position) + 1
        while left < right:
            mid = left + (right - left) // 2
            if isfail(mid):
                right = mid
            else:
                left = mid + 1
        return left - 1 # left is the min value to fail, so left-

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        res = 0
        l, r = 1, (position[-1] - position[0]) // (m - 1)
        
        while l <= r:
            mid = (l + r) // 2
            prev = position[0]
            ball = 1
            for i in position[1:]:
                if i - prev >= mid:
                    ball += 1
                    prev = i
                if ball == m:
                    break
            if ball == m:
                l = mid + 1
                res = mid
            else:
                r = mid - 1
        return res
        
                


class Solution:
    def maxDistance(self, pos: [int], m: int) -> int:
        pos.sort()
        N = len(pos)
        
        high = (pos[-1]-pos[0])//(m-1)
        low = 1
        
        def check(dist):
            cnt = 1
            loc = pos[0]
            for i in range(1, N):
                if pos[i]-loc>=dist:
                    cnt += 1
                    loc = pos[i]
                    if cnt == m:
                        return True
            return False
        
        while high!=low:
            mid = (high+low+1)//2
            if check(mid):
                low = mid
            else:
                high = mid-1
        
        return high
                
        
        
            
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        N = len(position)
        A = position
        A.sort()
        
        lo, hi = 1, A[-1] - A[0]
        while lo <= hi:
            mid = (lo + hi + 1) // 2
            
            prev = A[0]
            left = m - 1
            for i in range(1, N):
                if A[i] - prev >= mid:
                    prev = A[i]
                    left -= 1
                    if left == 0:
                        break
                        
            if left == 0:
                answer = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return answer
        


def solve(positions, m, target):
    p = positions[0]
    m -= 1
    for p2 in positions[1:]:
        if p2 - p >= target:
            m -= 1
            p = p2
        if m == 0:
            return True
    return False                            
    
class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        positions.sort()
        l, r = 0, positions[-1] - positions[0] 
        best = 0
        while l <= r:
            target = (l + r) // 2
            if solve(positions, m, target):
                l = target + 1
                best = max(best, target)
            else:
                r = target - 1
        return best                

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        n = len(position)
        
        def countBalls(d):
            n_balls, cur = 1, position[0]
            
            for i in range(1, n):
                if position[i] - cur >= d:
                    n_balls += 1
                    cur = position[i]
                
            return n_balls
        
        left = 1
        right = position[n-1] - position[0]
        
        while left <= right:
            mid = left + (right - left) // 2
            if countBalls(mid) >= m:
                left = mid + 1
            else:
                right = mid - 1
        return right

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        def ifvalid(diff,num_division):
            selected=0
            cur=position[0]
            for i,f in enumerate(position):
                if selected>=num_division:
                    return True
                if (f-cur)>=diff:
                    selected+=1
                    cur=position[i]
                else:
                    if i==len(position)-1:
                        return False
            return selected>=num_division
                    
                    
        
        def search(l,r):
            while l<r:
                mid=l+(r-l)//2
                if not ifvalid(mid,m-1):
                    r=mid
                else:
                    l=mid+1
            return l-1
        
        max_diff=(position[-1]-position[0])//(m-1) +1
        return search(1,max_diff+1)
                    
            
                    
                
                
                    
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def count(d):
            ans = 1
            pre_pos = position[0]
            
            for i in range(1, n):
                if position[i] - pre_pos >= d:
                    ans += 1
                    pre_pos = position[i]
            
            return ans
            
        n = len(position)
        position.sort()
        
        left = 1
        right = position[-1] - position[0]
        
        while left < right:
            mid = left + (right-left+1) // 2
            
            if count(mid) >= m:
                left = mid
            else:
                right = mid - 1
                
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def count_d(dis):
            ans, cur = 1, position[0]
            for i in range(1, len(position)):
                if position[i] - cur >= dis:
                    ans += 1
                    cur = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r-l)//2
            if count_d(mid) >= m:
                l = mid 
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def is_possible(gap,left):
            prev=position[0]
            for i in range(1,len(position)):
                if position[i]-prev>=gap:
                    prev=position[i]
                    left-=1
                if not left: return True
            return False
        position.sort()
        l,r,ans=0,position[-1],0
        while l<=r:
            gap=(r+l)//2
            if is_possible(gap,m-1):
                ans=gap
                l=gap+1
            else:
                r=gap-1
        return ans
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def is_possible(gap,left):
            prev=position[0]
            for i in range(1,len(position)):
                if position[i]-prev>=gap:
                    prev=position[i]
                    left-=1
                if not left: return True
            return False
        position.sort()
        l,r,ans=0,position[-1],0
        while l<=r:
            gap=l+(r-l)//2
            if is_possible(gap,m-1):
                ans=gap
                l=gap+1
            else:
                r=gap-1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # 最大间隙使用二分法查找
        # 检查最大间隙的合理性
        # 从一堆间隙中，寻找连续长度为dist的m个间隙
        interval = []
        sort_pos = sorted(position)
        for i in range(len(sort_pos)-1):
            interval.append(sort_pos[i+1]-sort_pos[i])
        
        def is_valid(dist,interval):
            ball = 1
            count = 0
            for i in interval:
                count += i
                if count>=dist:
                    ball += 1
                    count = 0
            if ball>=m:
                return True
            return False
        
        left = 1
        right = sum(interval)//(m-1)
        # 如果最优值停在right上，那么这个循环永远不能结束
        while left<right:
            mid = right - (right-left)//2
            if is_valid(mid,interval):
                left = mid
            else:
                right = mid - 1
        return left
            


class Solution:
    def fit_balls(self, positions, n, min_dist):
        
        last_position = positions[0]
        placement_count = 1
        
        for p in positions:
            if p - last_position >= min_dist:
                last_position = p
                placement_count += 1
                if placement_count >= n:
                    return True
                
        return False
        
    def maxDistance(self, position: List[int], m: int) -> int:
        pos = sorted(position)
        
        lo = 0
        hi = pos[-1]-pos[0]
        
        while lo < hi:
            mid = hi - (hi-lo) // 2
            can_fit = self.fit_balls(pos, m, mid)
            
            if not can_fit:
                hi = mid-1
            else:
                lo = mid
                
        
        return lo
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def valid(force):
            nonlocal position, m
            
            start = count = 0
            for index, value in enumerate(position):
                if value - force >= position[start]:
                    count += 1
                    start = index

            return count >= m - 1
        
        lo, hi = 1, position[-1] - position[0]
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            
            if valid(mid):
                lo = mid
            else:
                hi = mid - 1
        
        return lo

class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        
        positions.sort()
        
        
        def possible(positions,m,v):
            
            cur=0
            for i in range(1,len(positions)):
                
                if positions[i]-positions[cur]>=v:
                    m-=1
                    cur=i
                    if m==1: return True
            
            return m<=1
             
        left,right=1,positions[-1]-positions[0]
        
        ans=0
        while left<=right:
            
            v=(left+right)//2
            # print(possible(positions,m,v),m,v)
            if possible(positions,m,v):
                ans=v
                left=v+1
            else:
                right=v-1
        
        return ans

from math import ceil

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        minPos, maxPos = position[0], position[len(position) - 1]
        lo, hi = 0, maxPos - minPos
        curAns = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.canFitAllBalls(mid, m, position):
                curAns = max(curAns, mid)
                lo = mid + 1
            else:
                hi = mid - 1
        return curAns
                
    def canFitAllBalls(self, dist, m, position):
        prev = None
        for pos in position:
            if prev == None or (pos - prev >= dist):
                m -= 1
                prev = pos
            if m == 0:
                break
        return m == 0

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        positions = position
        positions.sort()
        n = len(positions)
        def f(d):
            prev = 0
            balls = 1
            for i in range(1, n):
                if positions[i] - positions[prev] >= d:
                    prev = i
                    balls += 1
                    if balls >= m:
                        return True
            return False
        lo, hi = 0, positions[-1] - positions[0]
        while lo < hi:
            mi = lo + (hi - lo + 1) // 2
            if f(mi):
                lo = mi
            else:
                hi = mi - 1
        return lo
        
                    
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:        
        ''' DP causing timeout 
        def get_max_force(pos, count):
            
            #print(f\"get_max_force pos_index {pos} posistion {position[pos]} count {count}\")
            if count <=1 :
                return float('inf')
            
            if dp[pos][count-1] > -1: 
                #print(\"saved time\")
                return dp[pos][count-1] 
            
            if n - pos == count:
                min_force = float('inf')
                for pos_index in range(pos+1, n):
                    min_force = min(min_force, position[pos_index]-position[pos_index-1])
                #print(f\"dp 3 pos_index {pos} position {position[pos]} count{count} : {dp[pos][count-1]}\")  
                dp[pos][count-1] = min_force
                return min_force
                        
            if count == 2:
                dp[pos][count-1] = position[-1] - position[pos]
                #print(f\"dp 2 pos_index {pos} position {position[pos]} position[-1] {position[-1]} count{count} : {dp[pos][count-1]}\")
                return dp[pos][count-1]
            
            max_force = 0
            
            for pos_index in range(pos+1, n):
                if n - pos_index < count - 1:
                    break
                max_force = max(max_force, min(position[pos_index]-position[pos], get_max_force(pos_index, count-1)))
            
            dp[pos][count-1] = max_force
            #print(f\"dp 1 pos_index {pos} position {position[pos]} count{count} : {max_force}\")
            return max_force
        
        n = len(position)
        position.sort()
        dp = [[-1] * m for _ in position]
        if m == n:
            return get_max_force(0, m)            
        
        if m == 2:
            return position[-1] - position[0]
        

        max_force = 0       
        for pos_index in range(0, n):
            max_force = max(max_force, get_max_force(pos_index, m))
        
        return max_force
        '''
        n = len(position)
        position.sort()
        def calc(d):#return number of balls while maintaining distance d
            #print(f\"calc {d}\")
            curr = position[0]
            ans = 1
            for i in range(1, n):
                if position[i] - curr >= d:
                    index = i
                    curr = position[i]
                    ans += 1
            #print(f\"return {ans}\")
            return ans
        
        l, r = 0, position[-1] - position[0]
        #d = r
        d = 0
        while l < r:
            
            #mid = (r + l + 1) // 2
            #print(f\"l {l} r{r} d {mid}\")
            mid = l + (r-l) // 2
            count = calc(mid)
            if count < m:
                r = mid
            else:
                l = mid + 1
            
            
            ''' 
            if count < m:
                r = mid - 1
            elif count >= m:
                l = mid
            '''
        #print(l, r)
        #print(f\"{calc(l)}\")
        #print(f\"{calc(l-1)}\")
        if calc(l) == m:
            return l
        else:
            return l - 1
                
                
        
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n= len(position)
        position.sort()
        if m==2:
            return position[-1]- position[0]
        cache={}
        def F(x):
            placed=1
            prev= position[0]
            for i in range(1, n):
                if position[i]- prev>= x:
                    placed+=1
                    prev= position[i]
                if placed== m:
                    return True
            return False
        def get_x():
            l= 1
            r= position[n-1]- position[0]
            while l<=r:
                mid= (l+r)//2
                if mid not in cache:
                    cache[mid]= F(mid)
                c= cache[mid]
                if c:
                    l= mid+1
                    ans= mid
                else:
                    r=mid-1
            return ans
        return (get_x())


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def canPlace(force):
            balls = 1
            curr_dist = curr_i = 0
            for i in range(1, len(position)):
                curr_dist = position[i] - position[curr_i]
                if curr_dist >= force:
                    curr_i = i
                    curr_dist = 0
                    balls += 1
            return balls
        position.sort()
        left, right = 0, position[-1] - position[0]
        while left < right:
            mid = (left + right + 1) // 2
            if canPlace(mid) < m:
                right = mid - 1
            else:
                left = mid
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        diff = position[-1] - position[0]
        right = diff // (m - 1)
        left = 1
        
        def condition(num):
            k = m - 1
            prev = position[0]
            for n in position[1:]:
                if n - prev >= num:
                    k -= 1
                    prev = n
                if k == 0:
                    return True
            return False
        
        while left < right:
            mid = left + (right - left) // 2
            # print(mid, condition(mid))
            if condition(mid):
                left = mid + 1
            else:
                right = mid
        if condition(left):
            return left
        else:
            return left - 1
        # print(left)
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # dp 一定超时
        #minimax的题目，基本上都是binary search + greedy helper function
        # 用count(d)表示：当最小的距离是d时，最多能够放的球的个数，目标就是去找count(d)==m时，最大的d
        # 用二分思想:
        # 当count(d)<m时，说明d太大了，有的球放不下
        # 当count(d)>m时，说明d太小了，还有更多的球能放
        
        position.sort()
        
        l = 1
        r = position[-1] - position[0]
        while l < r:
            mid = r - (r-l)//2
            if self.helper(mid, position) >= m:
                l = mid
            else:
                r = mid-1
        
        return l
    
    
    def helper(self, d, position):
        res = 1
        cur = position[0]
        for i in range(1, len(position)):
            if position[i] - cur >= d:
                cur = position[i]
                res += 1
        return res


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2: return position[-1] - position[0]
        l, r = 1, position[-1]
        ans = 0
        while l < r:
            mid = (l + r) // 2
            prev, balls = -1000000000, 0
            for p in position:
                if p - prev >= mid:
                    balls += 1
                    if balls == m: break
                    prev = p
            if balls == m:
                ans = mid
                l = mid + 1
            else:
                r = mid
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def count(d):
            res, prev=1, 0
            for i in range(1, n):
                if position[i]-position[prev]>=d:
                    prev=i
                    res+=1
            return res
        
        n=len(position)
        position.sort()
        l, r=1, position[-1]-position[0]
        while l<r:
            mid=(l+r)//2+1
            if count(mid)<m: r=mid-1
            else: l=mid
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position = sorted(position)
        low, high = 1, position[-1]
        ans = 0
        while low <= high:
            mid = low + (high - low) // 2
            prev = position[0]
            cnt = 1
            for pos in position[1:]:
                if (pos - prev) >= mid:
                    cnt += 1
                    prev = pos
            if cnt >= m:
                ans = max(ans, mid)
                low = mid + 1
            else:
                high = mid - 1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
#         1 2 3 4 5 6 7
#         | | | |     |
#         b     b     b
#         forces: 3, 3, 6
#         results = 3
        
#         1 2 3 4 5 ...... 100000000  m = 2
#         | | | | |            |
#         b                    b
#         result = 100000000 - 1
        
#         1 2 3 4 5 ...... 100    m = 3
#         | | | | |         |
#         b                 b
#               mid =  50
# distance = 0 1 2 3 4 99
#
#                mid = 25
# distance = 0 1 2 3 4 99 
#                mid = 11
# distance = 0 1 2 3 4 99 
#                mid = 5
# distance = 0 1 2 3 4 99 
#                mid = 4
# distance = 0 1 2 3 4 99

#         1 2 3 4 5 ...... 100    m = 4
#         | | | | |         |
#         b                 b
#               mid =  50
# distance = 0 1 2 3 4 99
#
#                mid = 25
# distance = 0 1 2 3 4 99 
#                mid = 12
# distance = 0 1 2 3 4 99 
#                mid = 6
# distance = 0 1 2 3 4 99 
#                mid = 3
# distance = 1 2 3 1 96
# mid = 1
# mid = 2


        def find_distance(mid_pos):
        
            count = 1
            pre = position[0]
            for i in range(1, len(position)):
                distance = position[i] - pre
                if distance >= mid_pos:
                    count += 1
                    pre = position[i]
            return count
        
        position = sorted(position)
        lo = 0
        hi = position[-1]
        while lo <= hi:
            mid = lo + (hi-lo)//2
            if find_distance(mid) >= m:
                lo = mid + 1
            else:
                hi = mid - 1
            
        return hi
       
        
        
        
        
        
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # 小心地使用暴力法求解: 可以尝试所有可能的间距, 找到最大的值
        # 两个观察:
        # 1. 要达到最优解第一个球一定放在第一个篮子里
        # 2. 如果最小间距为x时无法摆下所有球, 那么比x大的间距(x+1, x+2...)也不可能摆下所有球
        # 使用二分查找, 搜索能摆下所有球的间距
        # 需要确定: 二分查找的范围, 要满足的条件是啥
        # 二分查找模板->cond(k)成立的情况下最大化k
        position.sort()
        lo = 1
        # 显然最大间距不会超过这个值
        hi = position[-1] - position[0]
        while lo < hi:
            # 往右偏移的mid(corner case: lo=3, hi=4)
            mid = (lo + hi + 1) // 2
            if self.check(position, mid, m):
                lo = mid
            else:
                # mid不能满足条件
                hi = mid - 1
        # 当退出循环时hi是满足条件的最大值
        return hi

    # 检查最小间距为x时是否能放下所有的球
    def check(self, pos, x, m):
        remain_ball = m - 1 # 第一个球就放在第一个篮子里了
        n = len(pos)
        prev = 0
        for i in range(1, n):
            if pos[i] - pos[prev] >= x:
                remain_ball -= 1
                prev = i
                if remain_ball == 0:
                    return True
            else:
                continue
        return False


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        N = len(position)
        A = sorted(position)
        max_gap = A[-1] - A[0]
        min_gap = min(A[i] - A[i-1] for i in range(1, N))
        if m == 2:
            return max_gap
        if m == N:
            return min_gap
        
        def check(min_dist):
            prev = A[0]
            left = m - 1
            for i in range(1, N):
                if A[i] - prev >= mid:
                    prev = A[i]
                    left -= 1
                    if left == 0:
                        return True
            return False

        lo, hi = min_gap, max_gap
        while lo < hi:
            mid = (lo + hi + 1) // 2
            c = check(mid)
            if c:
                lo = mid
            else:
                hi = mid - 1
        return lo
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, int(math.ceil((position[-1] - position[0])/(m-1)))
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position, m):
        position.sort()
        N = len(position)
        l = math.inf
        for i in range(1, N):
            l = min(l, position[i] - position[i-1])
        r = position[-1] - position[0] + 1
        def check(k):
            last = position[0]
            res = 0
            for i in range(1, N):
                if position[i] - last >= k:
                    res += 1
                    last = position[i]
            return res
            
        
        while l < r:
            k = (l + r) // 2
            if check(k) <= m - 2:
                r = k
            else:
                l = k + 1
        return r - 1

class Solution:
    def maxDistance(self, arr: List[int], m: int) -> int:
        arr = sorted(arr)
        small = sys.maxsize
        for a, b in zip(arr, arr[1:]):
            small = min(small, b-a)
        def count(d):
            cur = arr[0]
            res = 1
            for i in range(1, len(arr)):
                if arr[i] - cur >= d:
                    res += 1
                    cur = arr[i]
            return res >= m
        
        def bs(l, r):
            if l > r: return 0
            mid = l + (r-l)//2
            if count(mid):
                return bs(mid+1, r) or mid
            else:
                return bs(l, mid-1)
                        
        return bs(small, arr[-1]-arr[0])
        
                    


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()        
        w = (position[-1] - position[0]) // (m-1)
        
        def count(w, m):
            idx = 0
            m -= 1
            for i in range(1, len(position)):
                if position[i] - position[idx] >= w:
                    idx = i
                    m -= 1
                
                if m == 0:
                    break
                    
            return m == 0


        if count(w, m):
            return w
        else:    
            l ,r = 0, w
            while l < r:
                mid = r - (r - l) // 2
                if count(mid, m):
                    l = mid
                else:
                    r = mid - 1
                
            return l
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev >= force:  # then that means we have that required force and we can keep a new ball here at position x
                    prev= x
                    balls_placed+=1  
                
            return(balls_placed>=m)
        
        lo,hi = 0, max(position)
        while lo<hi:
            mid = (lo+hi+1)//2
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(position, m, target):
            ct = 1
            j = 0
            k = 1
            flag = False
            while k < len(position) and ct < m:
                if position[k] -position[j] >= target:
                    ct += 1
                    if not flag:
                        kk = k
                        flag = True
                    j = k
                k += 1
            return (ct==m), kk
        
        position = sorted(position)
        max_p = position[-1]
        i = position[0]
        if m == 2:
            return max_p - i
        else:
            target = (max_p-i)//(m-1)
            ct = 1
            b, kk = check(position, m, target)
            if not b:
                while not b and kk!=1:
                    target = position[kk] - i 
                    target2 = position[kk-1] - i
                    b, kk = check(position, m, target2)
                if not b:
                    left = 1
                else:
                    left = position[kk] - i
                right = target
                while left + 1 < right:
                    target = (left + right)//2
                    if check(position, m, target)[0]:
                        left = target
                    else:
                        right = target
                target = left
            
            return target


class Solution:
    def put(self, position, d, m):
        n = 1
        curr = position[0]
        for i in range(1, len(position)):
            if position[i] - curr >= d:
                n += 1
                curr = position[i]
            if n >= m:
                return 1
        return 0
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        low, high = 0, position[-1]
        
        while low < high:
            mid = (high + low + 1) // 2
            comp = self.put(position, mid, m)
            
            if comp > 0:
                low = mid
            else:
                high = mid - 1
        return low

class Solution:
    def fit_balls(self, positions, n, min_dist):
        if n == 0:
            return True
        
        if len(positions) < 1:
            return False
        
        last_position = positions[0]
        placement_count = 1
        
        for p in positions:
            if p - last_position >= min_dist:
                last_position = p
                placement_count += 1
                
        return n <= placement_count
        
    def maxDistance(self, position: List[int], m: int) -> int:
        pos = sorted(position)
        
        lo = 0
        hi = pos[-1]-pos[0]
        
        while lo < hi:
            mid = hi - (hi-lo) // 2
            can_fit = self.fit_balls(pos, m, mid)
            
            if not can_fit:
                hi = mid-1
            else:
                lo = mid
                
        
        return lo
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 0, position[-1]
        while l + 1 < r:
            mid = (l + r) // 2
            if self.is_ok(position, mid, m):
                l = mid
            else:
                r = mid
        if self.is_ok(position, r, m):
            return r
        return l
    
    def is_ok(self, position, target, m):
        count = 1
        prev = position[0]
        for i in range(1, len(position)):
            diff = position[i] - prev
            if diff >= target:
                count += 1
                prev = position[i]
                
        return count >= m

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def helper(dist):
            count = 1
            prev = position[0]
            for i in range(1, len(position)):
                if position[i] - prev >= dist:
                    prev = position[i]
                    count += 1
            return count
                
        low = 1
        high = position[-1] - position[0]
        res = float('-inf')
        while low <= high:
            mid = low + (high - low) // 2
            if helper(mid) < m:
                high = mid - 1
            else:
                res = max(res, mid)
                low = mid + 1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        res = 0
        
        def feasible(distance):
            balls, curr = 1, position[0]
            for i in range(1, n):
                if position[i]-curr >= distance+1:### +1 to account for buckets
                    balls += 1
                    curr = position[i]                    
            return balls >= m
                           
        left, right = 0, position[-1]-position[0]
        while left<right:
            mid = left + (right-left)//2
            if feasible(mid):
                left = mid+1
            else:
                right = mid
        return left
        # return right

        
        
#         n = len(position)
#         position.sort()
        
#         def count(d):
#             ans, curr = 1, position[0]
#             for i in range(1, n):
#                 if position[i] - curr >= d:
#                     ans += 1
#                     curr = position[i]
#             return ans >= m
        
#         l, r = 0, position[-1] - position[0]
#         while l < r:
#             mid = r - (r - l) // 2   ###speed_up
#             # mid = l + (r-l)//2  ###TLE
#             if count(mid):
#                 l = mid
#             else:
#                 r = mid - 1
#         return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # Sort the array and evenly distribute the m balls
        position.sort()
        ans = top = (position[-1] - position[0]) // (m-1)
        down = 0
        while ans != down:
            if self._test(position, ans, m-1): down = ans
            else: top = ans
            ans = (top + down) // 2
            #print(ans, top, down)
        return down
        
    def _test(self, position, force, m):
        i = 0
        while i < len(position) and m > 0:
            if len(position) - 1 - i < m:
                return False
            total = 0
            while total < force:
                i += 1
                if i >= len(position): break
                total += position[i] - position[i-1]
            if total >= force: m -= 1
            #print(i, total, force, m)
        if m == 0: return True
        return False


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        def check(d):
            i, b = 0, 1
            for j in range(1, n):
                if position[j]-position[i] >= d:
                    b += 1
                    i = j
            return b >= m
        
        position = sorted(position)
        lo, hi = 1, position[-1]
        while lo < hi:
            mid = (lo+hi)//2
            if check(mid):
                lo = mid+1
            else:
                hi = mid
        return lo-1


class Solution:
    
    def nnpossible(self, pos, k, m) -> bool:
        prev = pos[0]
        k -= 1
        for i in pos:
            if i - prev >= m:
                k -= 1
                prev = i
            if k == 0:
                break
        return k == 0
    
    def maxDistance(self, position: List[int], k: int) -> int:
        position.sort()
        l = 0
        r = position[-1] + 1
        
        while r - l > 1:
            m = (l + r) // 2
            if self.nnpossible(position, k, m):
                l = m
            else:
                r = m
        return l
        
    
    
# TTTFFF


import numpy as np

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # Choose m values from n such that the minimum of the differences is maximized
        position.sort()
        
        def check(check_val):
            temp_m = m-1
            
            previous_pos = position[0]
            
            for p in position[1:]:
                if p - previous_pos >= check_val:
                    previous_pos = p
                    temp_m -= 1
                    if temp_m == 0:
                        return True
            return False
        
        l = 0   # min return value
        r = (position[-1] - position[0])//(m-1)+1 # max return value
        
        ret = l
        while l <= r:
            val = (l+r)//2
            if check(val):
                ret = max(ret, val)
                l = val + 1
            else:
                r = val-1
        return ret
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        def check(d):
            i, b = 0, 1
            for j in range(1, n):
                if position[j]-position[i] >= d:
                    b += 1
                    i = j
                    if b >= m:
                        return True
            return False
        
        position = sorted(position)
        lo, hi = 1, position[-1]
        while lo < hi:
            mid = (lo+hi)//2
            if check(mid):
                lo = mid+1
            else:
                hi = mid
        return lo-1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev >= force:  # then that means we have that required force and we can keep a new ball here at position x
                    prev= x
                    balls_placed+=1  
                if balls_placed ==m:
                    return(True)
                
            return(False)
        
        lo,hi = 0, max(position)
        while lo<hi:
            mid = (lo+hi+1)//2
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def canFindGaps(d):
            left = 0
            found = i = 1
            while i < len(position) and found < m:
                if position[i] - position[left] >= d:
                    found += 1
                    left = i
                i += 1
            return found == m
                
        
        position.sort()
        max_diff = position[-1] - position[0]
        if m == 2: return max_diff
        
        left, right = 1, max_diff//(m-1)
        while left < right:
            mid = (left+right)//2
            if canFindGaps(mid):
                left = mid + 1
            else:
                right = mid - 1
        
        if right < left:
            return right
        return left if canFindGaps(left) else left-1
        
            
        


class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        
        positions.sort()
        
        
        def possible(positions,m,v):
            
            cur=0
            for i in range(1,len(positions)):
                
                if positions[i]-positions[cur]>=v:
                    m-=1
                    cur=i
                    if m==1: return True
            
            return m<=1
             
        left,right=1,positions[-1]-positions[0]
        
        ans=0
        while left<=right:
            
            v=(left+right)//2
            if possible(positions,m,v):
                ans=v
                left=v+1
            else:
                right=v-1
        
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def isPossible(lst, m, force):
            pos = lst[0]
            for i in range(1, len(lst)):
                if lst[i] - pos >= force:
                    m -= 1
                    pos = lst[i]
            return m<2
        
        l = 0
        r = 1000000000
        position.sort()
        
        while l<r:
            mid = ((l+r) >> 1) + 1
            if isPossible(position,m,mid):
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        '''
        binary search
        similar to 278. First Bad Version
        '''
        n = len(position)
        position.sort()
        
        def isfail(mid):
            ans = 1
            curr = position[0] # alike greedy idea, we just put the first ball at position 0!
            for i in range(1, n):
                if position[i] - curr >= mid:
                    ans += 1
                    curr = position[i]
            return ans < m
        
        res = float('-inf')
        left = 1
        right = position[-1] - position[0]
        
        while left <= right:
            mid = (left+right)//2
            if isfail(mid):
                right = mid-1
            else:
                left = mid + 1
                res = max(res,mid)
        return res 

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        mx = position[-1]
        lo, hi = 1, mx

        def judge(x):
            pre, cnt = -mx, 0
            for p in position:
                if p - pre >= x:
                    pre = p
                    cnt += 1
                if cnt >= m:
                    return True
            return False

        while lo <= hi:
            mid = (lo+hi)//2
            if judge(mid):
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1]-position[0] + 1
        while l != r:
            mid = (l+r)//2 + (l+r)%2
            x = self.balls(position, mid)
            if x < m:
                r = mid-1
            elif x >= m:
                l = mid
        return l
        
    
    
    def balls(self, position, d):
        ans = 1
        cur = position[0]
        for i in range(1, len(position)):
            if position[i] - cur >= d:
                cur = position[i]
                ans += 1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        ###weirdly not working :(
        n = len(position)
        position.sort()
        res = 0
        
        def feasible(distance):
            balls, curr = 1, position[0]
            for i in range(1, n):
                if position[i]-curr >= distance+1:
                    balls += 1
                    curr = position[i]                    
            return balls >= m
                           
        left, right = 0, position[-1]-position[0]
        while left<right:
            mid = left + (right-left)//2
            if feasible(mid):
                left = mid+1
            else:
                right = mid
        return left

#         n = len(position)
#         position.sort()
        
#         def count(d):
#             ans, curr = 1, position[0]
#             for i in range(1, n):
#                 if position[i] - curr >= d:
#                     ans += 1
#                     curr = position[i]
#             return ans >= m
        
#         l, r = 0, position[-1] - position[0]
#         while l < r:
#             mid = r - (r - l) // 2   ###speed_up
#             # mid = l + (r-l)//2  ###TLE
#             if count(mid):
#                 l = mid
#             else:
#                 r = mid - 1
#         return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # binary search and check easy 
        # this function will check if all the balls can be placed at a distance of m or not. Then we just binary search all the 
        # distances. O(nlogn)
        position.sort()
        def check(mid):
            curr = position[0]
            placed = 1
            for i in range(len(position)):
                if position[i] >= curr + mid:
                    placed += 1
                    curr = position[i]
            return placed >= m
                
        l, r = 1, 10**9 + 1
        while l < r:
            mid = (l+r+1)//2
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l
        
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        if m==2:
            return max(position)-min(position)
        position.sort()
        l,r=1,(max(position)-min(position)+1)//(m-1)
        #print(l,r)
        def helper(mindist):
            #print(mindist)
            cnt=m-1
            cur=min(position)
            for i in position[1:]:
                if i-cur>=mindist:
                    cur=i
                    cnt-=1
                    if cnt==0:
                        return True
            return False
        if helper(r):
            return r
        while l<r:
            mid=l+(r-l)//2
            if helper(mid):
                l=mid+1
            else:
                r=mid
        #if helper(l):
            #return l
        #else:
        return l-1


def check(x,pos,m):
    c=0
    prev=-1000000000000000
    for i in range(len(pos)):
        if abs(pos[i]-prev)>=x:
            c+=1
            prev=pos[i]
    return c>=m
class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        n = len(pos)
        #print(pos)
        #pos = [-1000000000000000 pos + [10000000000000000]
        l=1
        r=pos[-1]
        while l<=r:
            mid =  l + (r-l)//2
            if check(mid,pos,m):
                l=mid+1
            else:
                r=mid-1
        if check(l,pos,m):
            return l
        else:
            return r
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        delta = []
        for i in range(len(position)-1):
            delta.append(position[i+1]-position[i])
            
        lo = min(delta)
        hi = sum(delta)
        m -= 1
        
        def isPossible(minForce):
            total = 0
            count = 0
            for d in delta:
                total += d
                if total >= minForce:
                    count += 1
                    total = 0
                    if count == m:
                        return True
            return False
        
        while lo <= hi:
            mid = (lo + hi) // 2
            if isPossible(mid):
                lo = mid + 1
            else:
                hi = mid - 1
        
        return lo-1


# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         #首先排序
#         position.sort()
#         print(position)
        
#         left = 1000000000
#         right = position[-1] - position[0]
#         for i in range(len(position)-1):
#             diff = abs(position[i] - position[i+1])
#             left = min(left, diff)
            
            
#         def check(diff, p, m):
#             m -= 1
#             last = p[0]
#             for i in range(1, len(p)):
#                 if abs(p[i] - last) >= diff:
#                     m -= 1
#                     last = p[i]
#                     if m <= 0:
#                         print(diff, \"True\")
#                         return True
#                 else:
#                     pass
#             print(diff, \"False\")
#             return False
            
#         print(\"left\", left, \"right\", right)
#         while left < right:
#             mid = (left + right) // 2
#             if check(mid, position, m) == True:
#                 left = mid
#                 if left == right:
#                     print(\"find 1\", left)
#                     break
#                 if left + 1 == right:
#                     if check(right, position, m):
#                         left = right
#                         print(\"find 2\", left)
#                     break
#             else:
#                 right = mid - 1
        
                
#         print(\"find 3\", left)
#         return left

# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         #首先排序
#         position.sort()
#         # print(position)
        
#         distance = [0 for _ in range(len(position)-1)]
#         for i in range(len(position)-1):
#             diff = position[i+1] - position[i]
#             distance[i] = diff
#         left = min(distance)
#         right = ceil((position[-1] - position[0]) / (m-1))
            
#         def check(diff, m):
#             m -= 1
#             pre_dis = 0
#             for i in range(0, len(distance)):
#                 if distance[i]+pre_dis >= diff:
#                     m -= 1
#                     if m <= 0:
#                         # print(diff, \"True\")
#                         return True
#                     pre_dis = 0
#                 else:
#                     pre_dis += distance[i]
#             # print(diff, \"False\")
#             return False
            
#         # print(\"left\", left, \"right\", right)
#         while left < right:
#             mid = (left + right+1) // 2
#             if check(mid, m) == True:
#                 left = mid
#                 # if left == right:
#                 #     print(\"find 1\", left)
#                 #     break
#                 # if left + 1 == right:
#                 #     if check(right, position, m):
#                 #         left = right
#                 #         print(\"find 2\", left)
#                 #     break
#             else:
#                 right = mid - 1
        
                
#         # print(\"find 3\", left)
#         return left
        
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        result = 0

        # can we place m balls each separated by x distance?
        def check(x) -> bool:
            nonlocal position, m

            last = position[0]
            placed = 1
            for pos in position:
                if pos - last >= x:
                    placed += 1
                    if placed >= m:
                        return True
                    last = pos

            return False



        first = 0
        last = int(ceil((position[-1] - position[0])/(m-1)))
        while first < last:

            mid = (first + last + 1)//2

            if check(mid):
                result = mid
                first = mid
            else:
                last = mid - 1

        return first

# 1552. Magnetic Force Between Two Balls
# Binary search

def can_distribute (baskets, ball_count, min_dist):
    last = []
    for basket in baskets:
        if not last or last[-1] + min_dist <= basket:
            last.append (basket)
            if len (last) == ball_count:
                return True
    return False

def first (a, b, p):
    if a >= b:
        return a
    elif p(a):
        return a
    elif not p(b-1):
        return b
    else:
        m = (a + b) // 2
        if p(m-1):
            return first (a, m, p)
        elif not p(m):
            return first (m, b, p)
        else:
            return m

def last (a, b, p):
    return first (a, b, lambda x: not p(x)) - 1

def max_dist (baskets, ball_count):
    baskets = sorted (baskets)
    theoretical_max_dist = (baskets[-1] - baskets[0]) // (ball_count - 1)
    return last (1, theoretical_max_dist + 1, lambda dist: can_distribute (baskets, ball_count, dist))

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        return max_dist(position, m)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        
        position = sorted(position)
        res = 0
            
        def check(n):
            count = 0
            cur = -1
            for i in range(len(position)):
                if cur < 0:
                    cur = position[i]
                    continue
                if position[i]- cur >= n:
                    cur = position[i]
                    count+=1
            return count+1
                
        l, r = 0, position[-1]- position[0]
        
        while l <= r:
            mid = (l+r)//2
            
            if check(mid) >= m:
                res = max(mid, res)
                l= mid+1
                
            else:
                r = mid-1
                
        return res


class Solution:
  def maxDistance(self, position: List[int], m: int) -> int:
    position.sort()
    def getCount(d: int) -> int:
      last, count = position[0], 1
      for x in position:
        if x - last >= d:
          last = x
          count += 1
      return count
    l, r = 0, position[-1] - position[0] + 1
    t = r
    while l < r:
      mid = l + (r - l) // 2
      if getCount(t - mid) >= m:
        r = mid
      else:
        l = mid + 1
    return t - l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        pos = sorted(position)
        l = 0
        r = pos[-1] - pos[0]
        while l < r:
            mid = (l + r + 1) // 2

            cum = pos[0]
            putted = 1
            for p in pos:
                if p >= cum + mid:
                    cum = p
                    putted += 1
            if putted >= m:
                l = mid
            else:
                r = mid - 1
        return l 

class Solution:
   def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        high = position[-1] - position[0]
        if m == 2:
            return high
        low = high
        for i in range(1, len(position)):
            low = min(position[i] - position[i - 1], low)
        if m == len(position):
            return low

        def count(step):
            c = 1
            pivot = 0
            for i in range(1, len(position)):
                if step <= (position[i] - position[pivot]):
                    c += 1
                    pivot = i
            return c
        res = None
        while low <= high:
            mid = low + (high - low) // 2
            num = count(mid)
            if num >= m:
                res = mid
                low = mid+1
            if num < m:
                high = mid-1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1] - position[0]
        while l < r:
            mid = (l + r) // 2
            if self.check(position, mid, m):
                l = mid + 1
            else:
                r = mid
        return l if self.check(position, l, m) else l-1
    
    def check(self, position, k, m):
        last_placed_position = None
        for i,p in enumerate(position):
            if i == 0 or p-last_placed_position >= k:
                m -= 1
                if m == 0:
                    return True
                last_placed_position = p
        return False


class Solution:
    def is_valid(self, arr, force, m):
        cnt = 1
        prev = arr[0]
        
        for i in range(1, len(arr)):
            if arr[i] - prev >= force:
                cnt += 1
                prev = arr[i]
            
            if cnt == m:
                return True
            
        return False
            
    
    def maxDistance(self, position: List[int], m: int) -> int:
        res = -1
        
        position.sort()
        
        left = 1
        right = position[len(position) - 1]
        
        while left + 1 < right:
            mid = (right - left) // 2 + left
            
            if (self.is_valid(position, mid, m)):
                # Too small
                left = mid
                res = max(res, mid)
            else:
                # Too big
                right = mid
                
        for i in range(left, right + 1):
            if self.is_valid(position, i, m):
                res = max(res, i)
            
        return res
            
                
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def small_enough(mid):
            count = prev = 0
            for i, p in enumerate(position):
                if i == 0:
                    count += 1
                elif p - prev >= mid:
                    count += 1
                else:
                    continue
                prev = p
            return count >= m
        
        l, h = 1, position[-1] - position[0]
        while l < h:
            mid = (l + h + 1) // 2
            if small_enough(mid):
                l = mid
            else:
                h = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev >= force:  
                    prev= x
                    balls_placed+=1  
                
            return(balls_placed>=m)
        
        lo,hi = 0, max(position)
        while lo<hi:
            mid = (lo+hi+1)//2
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        posSorted = position
        low = 1
        high = posSorted[-1]
        mid = (low+high)//2

        while low < high:
            if self.validForce(posSorted, m, mid):
               low = mid
            else:
                high = mid-1

            mid = high-(high-low)//2
        
        return low 

    def validForce(self, positions, m, mid):
        used = 0
        lastpos = 0
        for i, pos in enumerate(positions):
            if i == 0:
                used += 1
                continue
            if (pos - positions[lastpos]) >= mid:
                lastpos = i  
                used += 1
        if used >= m:
            return True

        return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        if m == 2:
            return position[-1] - position[0]
        
        def checkPossible(ans0):
            preV = position[0]
            leftM = m - 1
            for num in position[1:]:
                if num - preV >= ans0:
                    leftM -= 1
                    preV = num
                    if leftM == 0:
                        return True
            return False
        
        l = 0
        r = position[-1]
        ans = position[1]-position[0]
        while r > l:
            mid = (r+l)//2
            # print(l, r, mid)
            if checkPossible(mid):
                ans = mid
                l = mid + 1
            else:
                r = mid
        return ans
        
#         dp = {}
#         minDelta = [position[i]-position[i-1] for i in range(1, n)]
#         # print(position)
#         # print(minDelta)
#         for i in range(n-3, -1, -1):
#             if minDelta[i] > minDelta[i+1]:
#                 minDelta[i] = minDelta[i+1]
        
#         def placeABall(preI, m0):
#             if (preI, m0) in dp:
#                 return dp[(preI, m0)]
#             if m0 == 1:
#                 return position[-1] - position[preI]
#             if n-preI-1 == m0:
#                 subAns = minDelta[preI]
#                 dp[(preI, m0)] = subAns
#                 return subAns
#             subAns = 0
            
#             l = preI+1
#             r = n-m0
#             if position[l] - position[preI] >= placeABall(l, m0-1):
#                 subAns = placeABall(l, m0-1)
#             elif position[r] - position[preI] <= placeABall(r, m0-1):
#                 subAns = position[r] - position[preI]
#             else:
#                 while l < r:
#                     m = (l+r)//2
#                     temp = placeABall(m, m0-1)
#                     if position[m] - position[preI] < temp:
#                         l = m + 1
#                     elif position[m] - position[preI] > temp:
#                         r = m
#                     else:
#                         l = m
#                         break
#                 subAns = (min(position[l] - position[preI], temp))
#                 if l + 1 <= n-m0:
#                     subAns = max(subAns, (min(position[l+1] - position[preI], placeABall(l+1, m0-1))))
#                 if l - 1 >= preI + 1:
#                     subAns = max(subAns, (min(position[l-1] - position[preI], placeABall(l-1, m0-1))))
                    
#             # for i1 in range(preI+1, n-m0+1):
#             #     subAns = max(subAns, min(position[i1] - position[preI], placeABall(i1, m0-1)))
#             dp[(preI, m0)] = subAns
#             return subAns
        
#         return placeABall(0, m-1)


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        hi = position[-1] - position[0] + 1
        lo = 0
        
        def x(target):
            currMin = position[0] 
            count = 1
            
            for pos in position:
                if pos - currMin >= target:
                    currMin = pos
                    count += 1
                if count >= m:
                    return False
            return True
                    
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if x(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def distributable(n):
            pos = len(position) - 1
            balls = m
            while pos >= 0 and balls:
                balls -= 1
                np = position[pos] - n
                while pos >= 0 and position[pos] > np:
                    pos -= 1
            return not balls       
        position = sorted(position)
        lo, hi = 1, (position[-1] - position[0]) // (m -1) + 1
        ans = lo
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans        

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        
        l = 1
        r = position[-1] - position[0]
        
        def check(diff, m):
            ctr = 1
            prev = 0
            
            for i in range(1, len(position)):
                if ctr==m:
                    return True
                if position[i]-position[prev]>=diff:
                    ctr+=1
                    prev = i
                    
            if ctr==m:
                return True
            return False
        
        val = -10**10
        
        while l<=r:
            mid = (l+r)//2
            
            if check(mid, m):
                val = max(val, mid)
                l = mid+1
            else:
                r = mid-1
                
        return val

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n=len(position)
        position.sort()
        
        def count(d):
            cur=position[0]
            ans=1
            for i in range(1,n):
                if position[i]-cur>=d:
                    ans+=1
                    cur=position[i]
            return ans
        l,r=0,position[-1]-position[0]
        while l<r:
            mid=r-(r-l)//2
            if count(mid)>=m:
                l=mid
            else:
                r=mid-1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def distributable(n):
            pos = len(position) - 1
            balls = m
            while pos >= 0 and balls:
                balls -= 1
                np = position[pos] - n
                while pos >= 0 and position[pos] > np:
                    pos -= 1
            return not balls       
        position = sorted(position)
        lo, hi = 1, (position[-1] - position[0]) // (m -1) + 1
        ans = lo
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans   

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def isOK(x):
            rest = m - 1
            pre = position[0]
            for p in position[1:]:
                if p - pre >= x:
                    pre = p
                    rest -= 1
                    if rest == 0:
                        return True
            return False
        
        left = 1
        right = position[-1] - position[0]
        while left < right:
            mid = (left + right + 1) // 2
            # print(f'{mid=}')
            # print(f'{isOK(mid)=}')
            if isOK(mid):
                left = mid
            else:
                right = mid - 1
        return right


from array import array
class Solution:
   def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        position = array('i', position)
        high = position[-1] - position[0]
        low = high
        for i in range(1, len(position)):
            low = min(position[i] - position[i - 1], low)
        def count(step):
            c = 1
            pivot = 0
            for i in range(1, len(position)):
                if step <= (position[i] - position[pivot]):
                    c += 1
                    pivot = i
            return c
        res = None
        while low <= high:
            mid = low + (high - low) // 2
            num = count(mid)
            if num >= m:
                res = mid
                low = mid+1
            if num < m:
                high = mid-1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(arr, n, m, mid): 
            magnet=1
            pos=arr[0] 
            for i in range(1, n): 
                if arr[i]-pos>=mid: 
                    magnet+=1 
                    pos=arr[i] 
                    if magnet==m: 
                        return 1
            return 0

        position.sort() 
        l=0 
        n=len(position)
        r=position[n - 1] 
        res=0 
        
        while l<=r: 
            mid=(l+r)//2 
            if not check(position, n, m, mid): 
                r=mid-1
            else: 
                res=max(res, mid) 
                l=mid + 1
        return res 


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def count(d):
            ans = 1
            pos = position[0]
            for i in range(1,n):
                if position[i]-pos>=d:
                    ans+=1
                    pos = position[i]
            return ans
        
        l = 0
        r = position[-1] - position[0]
        
        while l<r:
            mid = (l+r+1)//2
            
            if count(mid)>=m: 
                l = mid
            else:
                r = mid-1
        
        return l        

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo,hi=1,position[-1]-position[0]
        while lo<hi:
            mi,t,y=(lo+hi+1)//2,1,position[0]
            for x in position:
                if x-y>=mi: y,t=x,t+1
            if t<m: hi=mi-1
            else: lo=mi
        return lo

class Solution:
    def maxDistance(self, position, m: int) -> int:
    # binary search and check easy
    # this function will check if all the balls can be placed at a distance of m or not. Then we just binary search all the
    # distances. O(nlogn)
        position.sort()

        def check(mid):
            curr = position[0]
            placed = 1
            for i in range(len(position)):
                if position[i] >= curr + mid:
                    placed += 1
                    curr = position[i]
            return placed >= m

        l, r = 1, 10 ** 9 + 1
        while l < r:
            mid = (l + r + 1) // 2
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l
        
            
            


class Solution:
    def maxDistance(self, a: List[int], m: int) -> int:        
        def check(d):
            x, k = 0, m            
            for i in range(len(a)):
                if a[i] >= x: 
                    x, k = a[i] + d, k - 1
                    if k == 0: break                             
            return k == 0            
        a.sort()                
        l, r = 1, (max(a) - min(a)) // (m-1)                        
        while l < r:
            d =  r - (r - l) // 2        
            if check(d): l = d
            else: r = d - 1                            
        return r if check(r) else l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n=len(position)
        
        def posb(t):
            k=0
            s=0
            for i in range(n-1):
                k+=position[i+1]-position[i]
                if k>=t:
                    k=0
                    s+=1
            
            return s>=m-1
                
        hgh=position[-1]-position[0]
        low=0
        while low<hgh:
            mid=hgh-(hgh-low)//2
            
            
          
          
            if posb(mid):
                low=mid
          
            else:
                hgh=mid-1
        return low
       
            
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # sort balls
        position.sort()
        # max number of balls that can preserve a min difference of diff between any two balls
        def count_balls(diff):
            nballs, cur = 1, position[0]
            for i in range(1, len(position)):
                if position[i] - cur >= diff:
                    nballs += 1
                    cur = position[i]
            return nballs
        # m can range from 1 to position[-1] - position[0]
        left, right = 1, position[-1] - position[0]
        while left <= right:
            mid = (left + right) // 2
            if count_balls(mid) >= m:
                left = mid + 1
            else:
                right = mid - 1
                
        return right


def count(position,m,n,d):
    ans,curr=1,position[0]
    for i in range(1,n):
        if position[i]-curr>=d:
            ans+=1
            curr = position[i]
            if ans==m:
                return True
    return False
    
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        l,r = 1,10**9+7
        res = -1
        while l<r:
            mid = (l+r)//2
            if count(position,m,n,mid):
                res = max(res,mid)
                l = mid+1
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        # Counts number of balls that can be placed into baskets if minimum distance is d
        # Find maximum d where count(d) == m
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
                
        return l

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        A.sort()
        n = len(A)
        l, r = 1, A[-1] - A[0]
        
        def get_m(d):
            res = 1
            i = 1
            prev = A[0]
            while i < n:
                if A[i] - prev >= d:
                    res += 1
                    prev = A[i]
                i += 1
            return res
        
        while l < r:
            mid = r - (r - l) // 2
            if get_m(mid) < m:
                r = mid - 1
            else:
                l = mid
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        length = len(position)
        position.sort()

        def count(d):
            minmax = 1
            curr = position[0]
            for i in range(1, length):
                if position[i] - curr >= d:
                    minmax += 1
                    curr = position[i]
            return minmax

        lo, hi = 0, position[-1] - position[0]
        while lo < hi:
            mid = hi - (hi - lo) // 2
            if count(mid) >= m:
                lo = mid
            else:
                hi = mid - 1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def ispossible(A,force,n):
            n-=1
            last=A[0]
            for i in range(1,len(A)):
                if n>0:
                    if A[i]-last>=force:
                        n-=1
                        last=A[i]
                else:
                    break
                    
            if n==0:
                return True
            return False
                        
            
                
                
            
            
        
        A=position
        A.sort()
        l=1
        r=A[-1]
        ans=1
        while r>=l:
            mid=(r+l)//2
            
            if ispossible(A,mid,m):
                ans=mid
                l=mid+1
            else:
                r=mid-1
                
        return ans
                
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1] - position[0] + 1
        
        def isInvalid(val):
            ball = 1
            previous = position[0]
            for p in position:
                if p - previous < val:
                    continue
                ball += 1
                previous = p
            return ball < m
        
        while l < r:
            mid = l + (r - l) // 2
            if isInvalid(mid):
                r = mid
            else:
                l = mid + 1
                
        return l - 1

class Solution:
    def maxDistance(self, a: List[int], m: int) -> int:        
        def check(d):
            x, k = 0, m            
            for i in range(len(a)):
                if a[i] >= x: 
                    x, k = a[i] + d, k - 1
                    if k == 0: break                             
            return k == 0
            
        a.sort()                
        l, r = 1, (max(a) - min(a)) // (m-1)                        
        while l+1 < r:
            d = (l + r) // 2            
            if check(d): l = d
            else: r = d - 1                            
        return r if check(r) else l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        high=position[-1]-position[0]
        low=1
        output=[0]
        k=[m]
        def check(distance):
            previous=-1
            m=k[-1]
            previous=position[0]
            m-=1
            if m==0:
                return True
            for i in range(1,len(position)):
                
               
                if position[i]-previous>=distance:
                    previous=position[i]
                    m-=1
                    if m==0:
                        break
            if m==0:
                return True
            return False
        
        def binary(low,high):
         
            mid=(low+high)//2
            
             
            if low>high:
                
                return
            if check(mid):
                
                
                output[0]=mid
               
                binary(mid+1,high)
            else:
                binary(low,mid-1)
        binary(low,high)
        return output[-1]

# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         #首先排序
#         position.sort()
#         print(position)
        
#         left = 1000000000
#         right = position[-1] - position[0]
#         for i in range(len(position)-1):
#             diff = abs(position[i] - position[i+1])
#             left = min(left, diff)
            
            
#         def check(diff, p, m):
#             m -= 1
#             last = p[0]
#             for i in range(1, len(p)):
#                 if abs(p[i] - last) >= diff:
#                     m -= 1
#                     last = p[i]
#                     if m <= 0:
#                         print(diff, \"True\")
#                         return True
#                 else:
#                     pass
#             print(diff, \"False\")
#             return False
            
#         print(\"left\", left, \"right\", right)
#         while left < right:
#             mid = (left + right) // 2
#             if check(mid, position, m) == True:
#                 left = mid
#                 if left == right:
#                     print(\"find 1\", left)
#                     break
#                 if left + 1 == right:
#                     if check(right, position, m):
#                         left = right
#                         print(\"find 2\", left)
#                     break
#             else:
#                 right = mid - 1
        
                
#         print(\"find 3\", left)
#         return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        #首先排序
        position.sort()
        # print(position)
        
        distance = [0 for _ in range(len(position)-1)]
        for i in range(len(position)-1):
            diff = position[i+1] - position[i]
            distance[i] = diff
        left = min(distance)
        right = position[-1] - position[0]
            
        def check(diff, m):
            m -= 1
            pre_dis = 0
            for i in range(0, len(distance)):
                if distance[i]+pre_dis >= diff:
                    m -= 1
                    if m <= 0:
                        # print(diff, \"True\")
                        return True
                    pre_dis = 0
                else:
                    pre_dis += distance[i]
            # print(diff, \"False\")
            return False
            
        # print(\"left\", left, \"right\", right)
        while left < right:
            mid = (left + right+1) // 2
            if check(mid, m) == True:
                left = mid
                # if left == right:
                #     print(\"find 1\", left)
                #     break
                # if left + 1 == right:
                #     if check(right, position, m):
                #         left = right
                #         print(\"find 2\", left)
                #     break
            else:
                right = mid - 1
        
                
        # print(\"find 3\", left)
        return left


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2:
            return position[-1]-position[0]
        print(position)
        left, right = 1, position[-1]-position[0]
        def valid(mid):
            count = 1
            last = position[0]
            for i in range(1, len(position)):
                if position[i] - last>=mid:
                    #print('-',position[i], last)
                    last = position[i]
                    count += 1
            #print(mid, count)
            return count>=m
        while left<right:
            mid = (right-left+1)//2+left
            #print(mid)
            if valid(mid):
                left = mid
            else:
                right = mid - 1
        return left

class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        def check(force, m):
            last = pos[0]
            m -= 1
            for i in range(1, len(pos)):
                if pos[i] - last >= force:
                    last = pos[i]
                    m -= 1
                if not m: return True
            return False

        left, right = 2, 10**9
        while left <= right:
            mid = left + (right - left) // 2
            if check(mid, m):
                left = mid+1
            else:
                right = mid-1
        return right

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        
        lo = 1
        hi = position[-1]
        
        while (lo < hi):
            mid = lo + (hi - lo) // 2 + 1
            
            if (self.can_be_put(position, m , mid)):
                lo = mid
            else:
                hi = mid - 1
                
        return lo
    
    def can_be_put(self, position, m, force):
        next_pos = position[0]
        
        for i in range(len(position)):
            if (next_pos <= position[i]):
                m -= 1
                next_pos = position[i] + force
                
        return m <= 0

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def check(force):
            k = m - 1
            pre = 0
            i = 1
            while i < n:
                while i < n and position[i] - position[pre] < force:
                    i += 1
                if i < n:
                    k -= 1
                if k == 0:
                    return True
                pre = i
                i += 1
            return False
        lo, hi = 1, position[-1]
        while lo < hi:
            mi = lo + (hi - lo) // 2
            if check(mi):
                lo = mi + 1
            else:
                hi = mi
        return lo - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        n = len(position)
        
        # count number of balls that can be put in basket with min_force d
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans    

        
        l, r = 1, position[-1] - position[0]
        while l < r:
            f = r - (r - l) // 2 # l + (r - l) // 2
            if count(f) >= m:
                l = f
            else:
                r = f - 1
        
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        N = len(position)
        def place(d):
            pre = position[0]
            idx = 1
            for i in range(m-1):
                while idx<N:
                    if position[idx]>=pre+d:
                        break
                    else:
                        idx+=1
                if idx==N:
                    return False
                else:
                    pre = position[idx]
                    
            return True
        
        l = 1
        r = position[-1]-position[0]
        while l<r:
            mid = (l+r+1)//2
            if place(mid):
                l = mid
            else:
                r = mid-1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l = 1
        r = (position[-1]-position[0])//(m-1)
        #print(l,r)
        while (l<=r):
            mid = (l+r)//2
            placed = 1
            distance = 0
            start = position[0]
            for i in range(1,len(position)):
                distance = position[i]-start
                if distance >= mid:
                    placed +=1
                    distance = 0
                    start = position[i]
            #print(placed)
            if placed >=m:
                answer = mid #we placed all balls
                l = mid +1
            else:
                r = mid -1
                
        return(answer)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        high=position[-1]-position[0]
        low=1
        output=[0]
        k=[m]
        def check(distance):
            previous=-1
            
            m=k[-1]
            for i in range(len(position)):
                if m==0:
                    break
                if i==0:
                    previous=position[0]
                    m-=1
                    continue
                if position[i]-previous>=distance:
                    previous=position[i]
                    m-=1
            if m==0:
                return True
            return False
        
        def binary(low,high):
         
            mid=(low+high)//2
            
             
            if low>high:
                
                return
            if check(mid):
                
                
                output[0]=mid
               
                binary(mid+1,high)
            else:
                binary(low,mid-1)
        binary(low,high)
        return output[-1]

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def isPossible(dist):
            count = 1
            prev = position[0]
            for x in position[1:]:
                if x - prev >= dist:
                    count += 1
                    prev = x
                    if count == m:
                        return True
            return False
        left, right = 0, position[-1]-position[0]
        while left <= right:
            mid = left + (right-left)//2
            if isPossible(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
    
        


class Solution:
    def possible(self, position, dist, m):
        prev = float('-inf')
        cnt = 0
        for x in position:
            if x < prev + dist:
                continue
            cnt += 1
            prev = x
        return cnt >= m
        
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        low, high = 0, max(position)
        while low + 1 < high:
            mid = (low + high) // 2
            if self.possible(position, mid, m):
                low = mid
            else:
                high = mid
        
        if self.possible(position, high, m):
            return high
        
        return low
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(f):
            nonlocal position
            nonlocal m
            nonlocal res
            for i in range(len(position)):
                balls_cnt = 1 
                last_ball_pos = 0

                for i in range(1, len(position)):
                    last_ball_val_pos = position[last_ball_pos]
                    curr_ball_val_pos = position[i]
                    cur_force = curr_ball_val_pos - last_ball_val_pos
                    if cur_force >= f:
                        balls_cnt +=1
                        last_ball_pos = i
                        if balls_cnt == m:  
                            res = max(res, f)                      
                            return True

                return False


        res = 0
        position.sort()
        left = 1
        right = position[-1]

        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                # add to answer, check if can do better increase mid and look up in right part
                left = mid + 1
            else:
                right = mid

        return res   
      


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        N = len(position)
        
        left, right = 0, position[-1] - position[0]
        
        while left + 1 < right:
            mid = int((right - left) / 2 + left)
            
            if self.count(mid, position) >= m:
                left = mid
            else:
                right = mid
        
        if self.count(right, position) == m:
            return right
        return left
    
    def count(self, n: int, position: List[int]) -> int:
        ans, curr = 1, position[0]
        
        for i in range(1, len(position)):
            if position[i] - curr >= n:
                curr = position[i] 
                ans += 1
                
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def good(d):
            c, prev = 1, 0
            for i in range(1,len(position)):
                if position[i] - position[prev] >= d:
                    c += 1
                    prev = i
                
                if c == 0:
                    break
                    
            return c
          
        position.sort()
        l, r = 0, position[-1] - position[0]
        
        while l <= r:
            mid = (r + l) // 2
            
            if good(mid) >= m:
                l = mid + 1
            
            else:
                r = mid - 1
                        
        return r

class Solution:
    def maxDistance(self,position, m) -> int:
        position.sort()
        l = 0
        r = position[-1]-position[0]

        def isValid(dist):
            used = 1
            curr = position[0]
            for j in range(1,len(position)):
                if position[j]-curr>=dist:
                    used+=1
                    curr = position[j]
            return used

        while l<r:
            # 1 2 3 4 5
            # l       r
            # l-> bigger
            # <-r smaller
            d = r-(r-l)//2
            used = isValid(d)
            if used>=m:
               l = d
            else:
                r = d-1
        return r


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position = sorted(position)
        
        def count(d, position):
            m_num, cur = 1, position[0]
            for p in position:
                if p - cur >= d:
                    m_num += 1
                    cur = p
            return m_num
        
        l = 0
        r = position[-1] - position[0]
        
        while l < r:
            mid = l + (r-l)//2
            m_num = count(mid+1, position)
            if m_num < m:
                r = mid
            else:
                l = mid + 1
        return l
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
#         n = len(position)
#         position.sort()
#         res = 0
        
#         def feasible(distance):
#             balls, curr = 1, position[0]
#             for i in range(1, n):
#                 if position[i]-curr >= distance+1:### +1 to account for buckets
#                     balls += 1
#                     curr = position[i]                    
#             return balls >= m
                           
#         left, right = 0, position[-1]-position[0]
#         while left<right:
#             mid = left + (right-left)//2
#             if feasible(mid):
#                 left = mid+1
#             else:
#                 right = mid
#         return left
#         # return right

 ############################################       
        
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans >= m
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2   ###speed_up
            # mid = l + (r - l) // 2  ###TLE
            print((l, r))
            if count(mid):
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
  def maxDistance(self, position: List[int], m: int) -> int:
    # we will binary search for the result
    position.sort()
    
    # the minimum possible distance between balls is 1
    lo = 1
    # the maximum possible distance is the distance from the end to the start
    hi = position[-1] - position[0]
    
    def isPossible(minDistance):
      remaining = m
      prev = float('-inf')
      for p in position:
        if p - prev >= minDistance:
          prev = p
          remaining -= 1
      return remaining < 1
    
    while lo < hi:
      mid = hi - ((hi - lo) >> 1)
      if isPossible(mid):
        lo = mid
      else:
        hi = mid - 1
    return lo
      
    


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        l,r = 1, position[-1]-position[0]
        res = r
        while l <= r:
            mid = (l+r)//2
            prev,i,cnt = position[0],1,m-1
            while i < n and cnt > 0:
                if position[i] - prev >= mid:
                    cnt -= 1
                    prev = position[i]
                i += 1
            if cnt > 0:
                r = mid - 1
            else:
                res = mid
                l = mid + 1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            num, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    num += 1
                    curr = position[i]
            return num
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        A.sort()
        def valid(i):
            cnt = 1
            cur = A[0]
            for x in A[1:]:
                if x - cur >= i:
                    cnt += 1
                    cur = x
                if cnt >= m:
                    return True
            return False
        
        #print(valid(1), valid(2), valid(3), valid(4))
        l, r = 1, A[-1]
        
        while l < r:
            mid = (l + r) // 2
            if valid(mid):
                l = mid + 1
            else:
                r = mid
        return l - 1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def isPossible(mid, m):
            m -= 1
            i = 1
            prev = position[0]
            while i < n and m:
                if position[i] - prev >= mid:
                    prev = position[i]
                    m -= 1
                i += 1
            return m == 0
        
        
        position.sort()
        n = len(position)
        lo = hi = position[-1] - position[0]
        for i in range(n - 1):
            lo = min(lo, position[i + 1] - position[i])
        ans = 0
        while lo <= hi:
            mid = lo + (hi - lo)//2
            if isPossible(mid, m):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        left,right = 0,position[-1]-position[0] # search space is sorted
        
        def count_balls(force):
            balls,prev = 1,position[0]
            for cur in position[1:]:
                if cur-prev >= force:
                    balls += 1
                    prev = cur
            return balls
            
        
        while left < right:
            # mid = left + (right-left)//2
            mid = right - (right-left) // 2
            # mid = (left+right+1)//2
            if count_balls(mid) >= m:
                left = mid
            else:
                right = mid - 1
        return left

            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def checkForce(force, positions, m):
            i, prev = 1, positions[0]
            while m > 0 and i < len(positions):
                while positions[i] - force < prev:
                    i += 1
                    if i >= len(positions): return False
                prev = positions[i]
                m -= 1
                i += 1
            return m <= 0
        
        l, r = 0, position[-1] 
        while l < r:
            mid = r - (r - l) // 2
            # force is acceptable, let's see if we can achieve a higher force 
            if checkForce(mid, position, m-1):
                l = mid
            else:
                r = mid - 1
        return l 


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def count(d):
            res = 1
            cur = position[0]
            for i in range(1, n):
                if position[i] - cur >= d:
                    res += 1
                    cur = position[i]
            return res
        n = len(position)
        position.sort()
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()        
        w = (position[-1] - position[0]) // (m-1)
        print(position)
        
        def count(w, m):
            idx = 0
            m -= 1
            for i in range(1, len(position)):
                if position[i] - position[idx] >= w:
                    idx = i
                    m -= 1
                
                if m == 0:
                    break
                    
            return m == 0


        if count(w, m):
            return w
        else:    
            l ,r = 0, w
            while l < r:
                mid = r - (r - l) // 2
                if count(mid, m):
                    l = mid
                else:
                    r = mid - 1
                
            return l
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def count(dist):
            last_pos = position[0]
            cnt = 1
            
            for pos in position:
                if pos - last_pos >= dist:
                    cnt += 1
                    last_pos = pos
            
            return cnt
        
        # Binary Search on the answer
        l = 1
        r = position[-1] - position[0]
        
        while l < r:
            mid = (l + r + 1) // 2
            if count(mid) < m:
                r = mid-1
            else:
                l = mid
        
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort() 
        def findcount(d):
            res = 1 
            current = position[0]
            i = 1
            while i < len(position):
                if position[i] >= current+d:
                    current = position[i]
                    i+=1 
                    res+=1 
                else :
                    i+=1 
            return res 
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if findcount(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
    
            
            
            
                
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n=len(position)
        res=-1
        
        left=position[0]
        right=position[n-1]
        while left<right:
            mid=(left+right)//2
            if self.isFeasible(position,mid,m):
                res=max(res,mid)
                left=mid+1
            else:
                right=mid
                
        if res==-1:
            left=0
            right=position[0]
            while left<right:
                mid=(left+right)//2
                if self.isFeasible(position,mid,m):
                    res=max(res,mid)
                    left=mid+1
                else:
                    right=mid

        return res
        
        
    def isFeasible(self,arr,mid,m):
        n=len(arr)
        pos=arr[0]
        count=1
        for i in range(1,n):
            if arr[i]-pos>=mid:
                pos=arr[i]
                count+=1
                if count==m:
                    return True
        return False
        


class Solution:
    def maxDistance(self, position, m):
        position.sort()
        N = len(position)
        l = math.inf
        for i in range(1, N):
            l = min(l, position[i] - position[i-1])
        r = position[-1] - position[0] + 1
        def check(k):
            last = position[0]
            res = 0
            for i in range(1, N):
                if position[i] - last >= k:
                    res += 1
                    last = position[i]
            return res
            
        
        while l < r:
            k = (l + r) // 2
            if check(k) < m - 1:
                r = k
            else:
                l = k + 1
        return r - 1
            
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n=len(position)
        def distance(d):
            p=0 # current position
            c=1 # count of balls put into basket
            while p<n-1:
                
                for i in range(p,n):
                    if position[i]-position[p]>=d:
                        c+=1
                        break
                p=i
                if c==m:
                    return True
            return False
        
        l,r=0,position[-1]
        while l<r:
            md=r-(r-l)//2
            #print(md,distance(md))
            if distance(md):
                l=md
            else:
                r=md-1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        
        position.sort()
        
        def place(d):
            print(d)
            ans =  1
            pos =  position[0]+d
            j =  1
            
            while pos <= position[-1]:
                while j < len(position) and position[j] < pos:
                    j += 1
                if j == len(position):
                    break
                ans += 1
                pos = position[j]+d
                j += 1
                
            print('ans')
            print(ans)
            return ans
        
        
        l = 0
        r = position[-1]-position[0]
        
        while l <= r:
            mid = (l+r)//2
            if place(mid)>=m:
                l = mid+1
            else:
                r = mid-1
                
        
        return l-1
            
                
            
                
                
        
        


class Solution:
    def maxDistance(self,position, m) -> int:
        position.sort()
        l = 0
        r = position[-1]-position[0]

        def isValid(dist):
            used = 1
            curr = position[0]
            for j in range(1,len(position)):
                if position[j]-curr>=dist:
                    used+=1
                    curr = position[j]
            return used

        while l<r:
            d = r-(r-l)//2
            used = isValid(d)
            if used>=m:
               l = d
            else:
                r = d-1
        return r


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo=0   
        hi=position[-1]-position[0]
        n=len(position)
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
                    
            
        while lo<hi:
            #mid= (lo+hi+1)//2
            mid=hi-(hi-lo)//2
            res=count(mid)
            if res>=m:
                lo=mid
            elif res<m:
                hi=mid-1
        return lo
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def check(d):
            i = 0
            j = 1
            for _ in range(m-1):
                while j < len(position) and position[j] - position[i] < d:
                    j += 1
                if j >= len(position):
                    return False
                i = j
                j = j + 1
            return True
        a = 1
        b = position[-1] - position[0]
        ans = 0
        while a <= b:
            c = (a + b) // 2
            if check(c):
                ans = c
                a = c + 1
            else:
                b = c - 1
        return ans

# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         #首先排序
#         position.sort()
#         print(position)
        
#         left = 1000000000
#         right = position[-1] - position[0]
#         for i in range(len(position)-1):
#             diff = abs(position[i] - position[i+1])
#             left = min(left, diff)
            
            
#         def check(diff, p, m):
#             m -= 1
#             last = p[0]
#             for i in range(1, len(p)):
#                 if abs(p[i] - last) >= diff:
#                     m -= 1
#                     last = p[i]
#                     if m <= 0:
#                         print(diff, \"True\")
#                         return True
#                 else:
#                     pass
#             print(diff, \"False\")
#             return False
            
#         print(\"left\", left, \"right\", right)
#         while left < right:
#             mid = (left + right) // 2
#             if check(mid, position, m) == True:
#                 left = mid
#                 if left == right:
#                     print(\"find 1\", left)
#                     break
#                 if left + 1 == right:
#                     if check(right, position, m):
#                         left = right
#                         print(\"find 2\", left)
#                     break
#             else:
#                 right = mid - 1
        
                
#         print(\"find 3\", left)
#         return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        #首先排序
        position.sort()
        # print(position)
        
        distance = [0 for _ in range(len(position)-1)]
        for i in range(len(position)-1):
            diff = position[i+1] - position[i]
            distance[i] = diff
        left = min(distance)
        right = ceil((position[-1] - position[0]) / (m-1))
            
        def check(diff, m):
            m -= 1
            pre_dis = 0
            for i in range(0, len(distance)):
                if distance[i]+pre_dis >= diff:
                    m -= 1
                    if m <= 0:
                        # print(diff, \"True\")
                        return True
                    pre_dis = 0
                else:
                    pre_dis += distance[i]
            # print(diff, \"False\")
            return False
            
        # print(\"left\", left, \"right\", right)
        while left < right:
            mid = (left + right+1) // 2
            if check(mid, m) == True:
                left = mid
                # if left == right:
                #     print(\"find 1\", left)
                #     break
                # if left + 1 == right:
                #     if check(right, position, m):
                #         left = right
                #         print(\"find 2\", left)
                #     break
            else:
                right = mid - 1
        
                
        # print(\"find 3\", left)
        return left


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        min_p, max_p = position[0], position[-1]
        
        def enough(x):
            prev, cnt = min_p, 1
            for i, p in enumerate(position):
                if p - prev >= x:
                    prev = p
                    cnt += 1
                    
                    if cnt >= m:
                        return True
            return False
        
        l, r = 1, max_p - min_p
        while l < r:
            mid = (l + r + 1) // 2
            if enough(mid):
                l = mid
            else:
                r = mid - 1
        return l
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        n = len(position)
        if m == 2: return position[-1] - position[0]
        
        
        lp = 0
        rp = (position[-1] - position[0])
        
        def can(gap):
            lidx = 0
            left = m - 1
            ptr = 1
            while left > 0 and ptr < n:
                if position[ptr] - position[lidx] >= gap:
                    left -= 1
                    lidx = ptr
                    ptr = lidx + 1
                    continue
                ptr += 1
            return left == 0
        
        ans = 0
        while lp < rp:
            mid = (lp+rp+1)//2
            if can(mid):
                lp = mid
            else:
                rp = mid-1
        return lp

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check_works(position, m, dist):
#             placing ball 1
            balls_to_place = m - 1
            last_ball_pos = 0
            for ind in range(last_ball_pos, len(position)):
                # print(position[ind])
                if position[ind] - position[last_ball_pos] >= dist:
                    balls_to_place -= 1
                    last_ball_pos = ind
                if balls_to_place == 0:
                    break
            if balls_to_place == 0:
                return 1
            else:
                return 0
            
        
#       let's try between 1 and 1000000000
        position.sort()
        lb = 1
        rb = 1000000000
        while (lb != rb - 1):
            ret = check_works(position, m, int((lb + rb)/2))
            
            if(ret == 0):
                rb = int((lb + rb)/2)
            else:
                lb = int((lb + rb)/2)
            
            print(lb,rb)
        return lb

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def count(d):
            c, cur = 1, position[0]
            for i in range(1, n):
                if position[i] - cur >= d:
                    c += 1
                    cur = position[i]
            
            return c
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
            
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def possible(force):
            prev = float('-inf')
            balls_placed = 0
            for x in position:
                if x-prev < force:
                    continue
                
                prev= x
                balls_placed+=1  
                
            return(balls_placed>=m)
        
        lo,hi = 0 , max(position)
        while lo<hi:
            mid = lo+hi+1>>1
            if possible(mid):
                lo=mid
                
            else:
                hi=mid-1
                
        return(lo)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def check(dis):
            num = 0
            presum = 0
            for i in range(1, n):
                presum += position[i] - position[i-1]
                if presum >= dis:
                    presum = 0
                    num += 1
            return num
        
        l, r = 0, position[-1] - position[0]
        while l < r-1:
            mid = (l + r) // 2
            if check(mid) >= m-1:
                l = mid
            else:
                r = mid - 1
        return r if check(r) >= m-1 else l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l = 1
        r = (position[-1]-position[0])//(m-1)
        #print(l,r)
        while (l<r):
            mid = (l+r)//2 +1
            placed = 1
            distance = 0
            start = position[0]
            for i in range(1,len(position)):
                distance = position[i]-start
                if distance >= mid:
                    placed +=1
                    distance = 0
                    start = position[i]
            #print(placed)
            if placed >=m:
                #answer = mid #we placed all balls
                l = mid 
            else:
                r = mid -1
                
        return(l)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        # diffs = [position[i] - position[i-1] for i in range(1, n)]
        n = len(position)
        def check(target_min_force):
            put_count = 1
            cur_force = 0
            for i in range(1, n):
                cur_force += position[i] - position[i-1]
                if cur_force >= target_min_force:
                    cur_force = 0 
                    put_count += 1
                    if put_count == m:
                        return True
            return False
                
        l, r = -1, position[-1] - position[0] + 1
        while r - l > 1:
            mid = (l + r) // 2
            if check(mid):
                l = mid
            else:
                r = mid
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def guess(position, m, guess):
            placed = 1
            last = position[0]
            i = 1
            while i < len(position):
                #print(position[i], last, placed, m)
                if position[i] - last >= guess:
                    placed += 1
                    last = position[i]
                
                if placed == m:
                    return True
                
                i += 1
            
           # print(\"final \", placed, m)
            return placed >= m
        
        position.sort()
        l = 0
        r = position[-1] - position[0]
        # l: checked OK
        # r: haven't check
        while l < r:
            mid = (l + r + 1) // 2
            #print(l, mid, r)
            if guess(position, m, mid):
                #print(\"guess OK\", mid)
                l = mid
            else:
                r = mid - 1
        
        return l
    
    
    #placed = 1, last = 1, i = 1
    # 
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position) 
        
        def checkForce(force, positions, m):
            prev = positions[0]
            i = 1
            while m > 0 and i < len(positions):
                while positions[i] - force < prev:
                    i += 1
                    if i >= len(positions): return False
                m -= 1
                prev = positions[i]
                i += 1
            return m <= 0
        
        # print(checkForce(2, position, m - 1))
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            # force is acceptable, let's see if we can achieve a higher force 
            if checkForce(mid, position, m-1):
                l = mid
            else:
                r = mid - 1
        return l 


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def bs(mid, m):
            pre = position[0]
            m -= 1
            
            for x in position:
                if x - pre >= mid:
                    pre = x
                    m -= 1
                    if m == 0:
                        return True
            
            if m == 0:
                return True
            else:
                return False
                
        
        l = 1
        r = 10 ** 9
        
        position.sort()
        
        while l < r:
            mid = l + (r - l) // 2
            if bs(mid, m):
                l = mid + 1
            else:
                r = mid
        
        return l - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def count(d):
            res = 1
            curr = position[0]
            for i in range(1,n):
                if position[i] - curr >= d:
                    res += 1
                    curr = position[i]
            return res
        l = 0
        r = position[-1] - position[0]
        while l < r:
            mid = l + (r-l) // 2 + 1
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # binary search on answer
        n = len(position)
        position.sort()
        left = 1
        right = max(position)
        while right - left > 1:
            mid = (left + right) // 2
            if self.ok(position, m, mid):
                left = mid
            else:
                right = mid
        if self.ok(position, m, right):
            return right
        elif self.ok(position, m, left):
            return left
        
    def ok(self, position, m, force):
        # first one at the 
        n = len(position)
        stack = [position[0]]
        i = 0
        while i < n:
            if position[i] - stack[-1] >= force:
                stack.append(position[i])
            i += 1
        return len(stack) >= m


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def distributable(n):
            pos = position.copy()
            balls = m
            while pos and balls:
                balls -= 1
                np = pos[-1] - n
                while pos and pos[-1] > np:
                    pos.pop()
            return not balls       
        position = sorted(position)
        lo, hi = 1, (position[-1] - position[0]) // (m -1) + 1
        ans = lo
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans        

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort() 
        
        left = 1
        right = (position[-1] - position[0]) // (m-1)
        
        def placeable(gap):
            count = 0
            x = -gap
            for n in position:
                if n-x >= gap:
                    count +=1 
                    x = n
                    if count == m:
                        return True 
            return False 
                
    
        while left < right:
            mid = (left + right + 1) // 2
            if placeable(mid):
                left = mid
            else:
                right = mid - 1
                
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        highest_f = int((position[-1] - position[0]) / (m - 1))
        def helper(position, m, high_f, low_f, curr_f):
            selected_pos = [position[0]]
            for i in position:
                if i - selected_pos[-1] >= curr_f:
                    selected_pos.append(i)
            if high_f > low_f + 1:
                if len(selected_pos) < m:
                    new_curr_f = int((low_f + curr_f) / 2)
                    return helper(position, m, curr_f, low_f, new_curr_f)
                else:
                    new_curr_f = int((curr_f + high_f) / 2)
                    return helper(position, m, high_f, curr_f, new_curr_f)
            else:
                if len(selected_pos) < m:
                    return low_f
                else:
                    return curr_f
        return int(helper(position, m, highest_f, 1, highest_f))

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def c(p,m,d):
            b=m-1
            l=len(p)
            acc=0
            for i in range(1,l):
                acc+=p[i]-p[i-1]
                if acc>=d:
                    acc=0
                    b-=1
                if b==0:
                    return True
            return False
        low=1
        high=max(position)
        mid=0
        position.sort()
        while low<=high:
            mid=(low+high)//2
            if c(position,m,mid):
                low=mid+1
            else:
                high=mid-1
        return high

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def distance(d):
            p=0 # current position
            c=1 # count of balls put into basket
            while p<len(position)-1:
                
                for i in range(p,len(position)):
                    if position[i]-position[p]>=d:
                        c+=1
                        break
                    
                p=i
                
                if c==m:
                    return True
            return False
        l,r=0,position[-1]
        while l<r:
            md=r-(r-l)//2
            #print(md,distance(md))
            if distance(md):
                l=md
            else:
                r=md-1
        return l

class Solution:

  def verify(self, position: List[int], dis: int, balls: int) -> bool:
    result = True
    start = position[0]
    cur = 1
    counter = 1
    while cur < len(position):
      if position[cur] >= start + dis:
        start = position[cur]
        counter += 1
        if counter >= balls:
          return True
      cur += 1

    return False

  def maxDistance(self, position: List[int], m: int) -> int:

    result = 0
    position = sorted(position)
    minvalue = sys.maxsize
    maxvalue = -sys.maxsize
    for value in position:
      minvalue = min(minvalue, value)
      maxvalue = max(maxvalue, value)

    left = 1
    right = maxvalue - minvalue
    while left <= right:
      mid = left + (right - left) // 2
      checked = self.verify(position, mid, m)
      if checked:
        left = mid + 1
        result = mid
      else:
        right = mid - 1

    return result


#!/usr/bin/env python
# -*- coding: utf-8 -*-

from typing import List, Dict


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        a = position
        a.sort()
        M = m

        def isok(m):
            c = 0
            prev = - (1 << 30)
            for x in a:
                if x - prev >= m:
                    c += 1
                    prev = x
            return c >= M

        l = 0
        r = 10 ** 9
        while l < r:
            m = (l + r + 1) // 2
            if isok(m):
                l = m
            else:
                r = m - 1
        return l


def _case(*a):
    assert Solution().maxDistance(*a[:-1]) == a[-1]
    pass


def test():
    _case([1, 100], 2, 99)
    _case([1,2,3,4,7], 3, 3)
    _case([5,4,3,2,1,1000000000], 2, 999999999)
    pass


from collections import deque

class Solution:
    def helper(self, minforce, position, m):
        #returns if minforce is valid or not
        counter = 1
        prev = position[0]
        i = 1
        while i < len(position) and counter < m:
            if position[i] - prev < minforce:
                i += 1
            else:
                counter += 1
                prev = position[i]
                i += 1
        if counter == m:
            return True
        else:
            return False
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left = 1
        right = position[-1] - position[0]
        if m==2:
            return right
        while left < right:
            mid = left + (right - left)//2
            #print(mid)
            if self.helper(mid, position, m):
                left = mid + 1
            else:
                right = mid
        return left-1

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        n = len(A)
        A.sort()
        
        def balls(d):
            count, cur = 1, A[0]
            
            for i in range(1, len(A)):
                if A[i] - cur >= d:
                    count += 1
                    cur = A[i]
            return count
        
        
        l, r = 1, A[-1] - A[0]
        
        while l < r:
            mid = (l + r + 1) // 2
            
            if balls(mid) >= m:
                l = mid
            else:
                r = mid - 1
                
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def num(dist):
            count = 1
            curr = position[0]
            for i in range(1, n):
                if position[i] - curr >= dist:
                    count += 1
                    curr = position[i]
            return count
        
        start = 0
        end = position[-1] - position[0]
        res = 0
        while start < end:
            mid = (start + end) // 2
            if num(mid) >= m:
                start = mid + 1
                res = mid
            else:
                end = mid
        if num(start) >= m:
            return start
        else:
            return start - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(position,mid):
            i=position[0]
            count=0
            for j in position:
                if((j-i)>=mid):
                    count+=1
                    i=j
            return count+1
        l=0
        position.sort()
        r=position[-1]
        while(r>(l+1)):
            mid=math.ceil((l+r)/2)
            print(mid)
            k=check(position,mid)
            if(k<m):
                r=mid
            else:
                l=mid
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1] - position[0] + 2
        ans = 0
        while l < r:
            mid = (l+r+1) //2
            cnt, i, j = 1, 1, 0
            while i < len(position):
                if position[i] - position[j] >= mid:
                    cnt += 1
                    j = i
                i += 1
            if cnt >= m:
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = (r - l + 1) // 2 + l
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left, right = 0, position[-1] - position[0]

        def check(dist):
            pre = position[0]
            n = m - 1
            i = 1
            while n:
                while i < len(position) and position[i] - pre < dist:
                    i += 1
                if i >= len(position): return False
                pre = position[i]
                i += 1
                n -= 1
            return True

        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return left - 1

class Solution:
    def _MaxPossibleForce(self, position):
        return position[-1] - position[0]
    
    def _GetNumAssignedBallsForGivenForce(self, position, force):
        i = 1
        assigned = 1
        # 0th item is the first ball
        last_assigned_position = 0
        while i < len(position):
            if position[i] - position[last_assigned_position] >= force:
                assigned += 1
                last_assigned_position = i
            i += 1
        return assigned
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        max_force = self._MaxPossibleForce(position)
        min_force = 1 # as m <= len(position)
        while min_force <= max_force:
            search_force = (min_force + max_force)//2
            num_assigned = self._GetNumAssignedBallsForGivenForce(position, search_force)
            if num_assigned < m:
                max_force = search_force - 1
            else:
                min_force = search_force + 1
        return max_force


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(position, d, m):
            last = position[0]
            balls = m - 1
            i = 1
            while balls and i < len(position):
                if position[i] - last < d:
                    i += 1
                else:
                    last = position[i]
                    balls -= 1
            return balls == 0
                                  
        position.sort()
        hi = position[-1]
        lo = 1

        while lo < hi:
            mi = (lo + hi + 1) // 2
            if check(position, mi, m):
                lo = mi
            else:
                hi = mi - 1
        return lo


#829
class Solution:
  def maxDistance(self, arr: List[int], m: int) -> int:
    arr.sort()
    low = 1
    high = arr[-1] - arr[0]
    
    def place(limit):
      prev = -1e10
      j = 0
      for i in range(m):
        while j < len(arr) and arr[j] - prev < limit:
          j += 1
        if j == len(arr):
          return False
        prev = arr[j]
        j += 1
        
      return True
    
    while low <= high:
      cur = int((low + high) / 2)
      #print(low, high, cur, place(cur))
      if place(cur):
        low = cur + 1
      else:
        high = cur - 1
    return high


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def helper(d):
            cnt = 1
            cur = position[0]
            for i in range(1, len(position)):
                if cur + d <= position[i]:
                    cur = position[i]
                    cnt += 1
            return cnt
        
        l, r = 0, position[-1] - position[0]
        res = -float('inf')
        while l <= r:
            # print(l, r)
            # if l == r and helper(l) == m:
            #     return l
            mid = (l + r) >> 1
            if helper(mid) == m:
                res = max(mid, res)
                l = mid + 1
            elif helper(mid) > m:
                # res = max(mid, res)
                l = mid + 1
            else:
                r = mid - 1
        return max(res, l-1)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(threshold):
            last = position[0]
            count = 1
            for p in position[1:]:
                if p - last >= threshold:
                    count += 1
                    last = p
                if count == m:
                    return True
            return False
            
        # binary search for max distance, l, r indicates distance
        position.sort()
        l, r = 1, position[-1]-position[0]

        while l <= r:
            mid = l + (r-l)//2
            if  check(mid):
                l = mid + 1
            else:
                r = mid - 1

        return r

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # m表示球的数量
        # 寻找m-1个空隙，来满足距离要求
        def dist_valid(interval, k):
            count,k_count = 0,0
            for i in interval:
                count += i
                if count>=k:
                    count = 0
                    k_count += 1
                    if k_count>=m-1:
                        return True
            return False
            
        interval = []
        sort_pos = sorted(position)
        for i in range(len(sort_pos)-1):
            interval.append(sort_pos[i+1]-sort_pos[i])
        left = 1
        right = (max(sort_pos)-min(sort_pos))//(m-1)
        while left<right:
            mid = right - (right-left)//2
            if dist_valid(interval,mid):
                left = mid
            else:
                right = mid - 1
        return left


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, cur = 1, position[0]
            for i in range(1, n):
                if position[i] - cur >= d:
                    ans += 1
                    cur = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        
        while l < r:
            mid = l + (r - l + 1)// 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
                
        return l

import bisect
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        def possible(gap):
            prev = position[0]
            idx = 0
            left = m - 1
            while left > 0:
                idx = bisect.bisect_left(position, prev+gap, idx + 1, n)
                if idx >= n:
                    return False
                else:
                    prev = position[idx]
                    left -= 1
            return True
        
        position.sort()
        min_gap = 1
        max_gap = position[-1] - position[0]
        while min_gap <= max_gap:
            cur_gap = (min_gap + max_gap) // 2
            if possible(cur_gap):
                # print(\"possible\", cur_gap)
                min_gap = cur_gap + 1
            else:
                # print(\"impossible\", cur_gap)
                max_gap = cur_gap - 1
                
        return min_gap - 1
    
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo = 1
        hi = position[-1] - position[0]
        def count(dis):
            res = 1
            i = 0
            curr = 0
            while i < len(position):
                if position[i]-position[curr] >= dis:
                    res += 1
                    curr = i
                i += 1
            return res
        # def count(d):
        #     ans, curr = 1, position[0]
        #     for i in range(1, len(position)):
        #         if position[i] - curr >= d:
        #             ans += 1
        #             curr = position[i]
        #     return ans
        while lo < hi:
            mid = hi-(hi-lo)//2
            if count(mid) >= m:
                lo = mid
            else:
                hi = mid-1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        left,right = 0,position[-1]-position[0] # search space is sorted
        
        def count_balls(force):
            balls,prev = 1,position[0]
            for cur in position[1:]:
                if cur-prev >= force:
                    balls += 1
                    prev = cur
            return balls
            
        
        while left < right:
            # mid = left + (right-left)//2
            mid = right - (right-left) // 2
            # mid = (left+right+1)//2
            if count_balls(mid) >= m:
                left = mid
            else:
                right = mid - 1
        return left
            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        def is_possible(threshold):
            count = 0
            prev = -math.inf 
            for x in position:
                if x - prev >= threshold:
                    count += 1
                    prev = x
            return count >= m

        span = position[-1] - position[0]
        lo, hi = 0, span
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if is_possible(mid):
                lo = mid 
            else:
                hi = mid - 1
        return lo

class Solution:
    # min-max, dp?
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def feasible(dist):
            placed, pos = 0, 0
            prev = float('-inf')
            while pos < len(position):
                if position[pos] - prev >= dist:  # can place one more
                    placed += 1
                    prev = position[pos]
                pos += 1
                if placed == m:
                    return True
            return False
                
        
        left, right = 1, position[-1]
        while left < right:
            dist = (left + right) // 2
            if feasible(dist):
                left = dist + 1
            else:
                right = dist
                
        return left - 1
        
                
                
                
                
        


class Solution:
    def maxDistance(self, position, m):
        position = sorted(position)
        start, end = 1, position[-1] - position[0]
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.check(position, m, mid):
                start = mid
            else:
                end = mid
        if self.check(position, m, end):
            return end
        if self.check(position, m, start):
            return start
    
    def check(self, position, m, delta):
        n = len(position)
        i = 1
        j = 1
        last = position[0]
        while i <= m - 1 and j <= n - 1:
            if position[j] >= last + delta:
                last = position[j]
                i += 1
            j += 1
        return i == m

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        A, n = sorted(A), len(A)
        left, right = 0, A[-1] - A[0]
        while left < right:
            mid = (right + left + 1) // 2
            ct, idx = 1, 0
            for i in range(1, n):
                if A[i] - A[idx] >= mid:
                    ct += 1
                    idx = i
            if ct < m:
                right = mid - 1
            else:
                left = mid
        return right

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def num_balls(min_dist: int) -> int:
            ans, curr = 1, 0
            
            for i in range(1,n):
                if position[i] - position[curr] >= min_dist:
                    ans += 1
                    curr = i
            return ans
        
        l, r = 0, position[n-1] - position[0]
        
        while l < r:
            mid = r - (r - l) // 2
            
            if num_balls(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo,hi = 1,(position[-1]-position[0])//(m-1) + 1
        res = 0
        
        
        def possible(gap):
            balls = m
            prev = None
            for i in range(len(position)):
                if not prev:
                    prev = position[i]
                    balls-=1
                else:
                    if abs(prev - position[i])<gap:
                        continue
                    else:
                        prev = position[i]
                        balls-=1
            if balls<=0:
                return True
            return False
        
        while lo<=hi:
            # print(lo,hi)
            mid = (lo+hi)//2
            
            if possible(mid):
                res = mid
                lo = mid+1
            else:
                hi = mid-1
                
        return res

class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        positions.sort()
        
        def possible(force):
            placed = 0
            pos = -math.inf
            
            for p in positions:
                if p - pos >= force:
                    placed += 1
                    pos = p
            
            return placed >= m
            
        (lo, hi) = (0, positions[-1])
        
        while lo <= hi:
            mid = (lo + hi) // 2
            if possible(mid):
                lo = mid + 1
            else:
                hi = mid - 1
                
        return hi

def pos(mid, position, m):
    res = 1
    curr_pos = 0
    for i in range(1, len(position)):
        if position[i] - position[curr_pos] >= mid:
            curr_pos = i
            res += 1
            if res == m:
                return True
    return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l = 0
        h = position[-1] - position[0]
        res = 0
        while l <= h:
            mid = int((h + l) / 2)
            if pos(mid, position, m) == False:
                h = mid - 1
            else:
                res = max(res, mid)
                l = mid + 1
        return res

class Solution:
    def _MaxPossibleForce(self, position):
        return position[-1] - position[0]
    
    def _AssignBallsWithKDistance(self, position, force):
        i = 1
        assigned = 1
        # 0th item is the first ball
        last_assigned_position = 0
        while i < len(position):
            if position[i] - position[last_assigned_position] >= force:
                assigned += 1
                last_assigned_position = i
            i += 1
        return assigned
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        max_force = self._MaxPossibleForce(position)
        min_force = 1
        print((self._AssignBallsWithKDistance(position, 4)))
        while min_force <= max_force:
            search_force = (min_force + max_force)//2
            num_assigned = self._AssignBallsWithKDistance(position, search_force)
            if num_assigned < m:
                max_force = search_force - 1
            else:
                min_force = search_force + 1
        return max_force


#https://leetcode.com/problems/magnetic-force-between-two-balls/discuss/854038/Beginner-Friendly-solution-or-Explained-with-time-complexity-analysis
    
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def check(dist):
            prev = position[0]
            cnt = 1
            idx = 0
            while idx<len(position):
                curr = position[idx]
                if curr-prev>=dist:
                    cnt += 1
                    prev = curr
                idx += 1
                if cnt>m:
                    break
            return cnt
        
        position.sort()
        L = 1
        R = position[-1]-position[0]
        
        while L<R:
            # print ('a ', L, R)
            if L==R-1:
                if check(R)>=m:
                    return R
                else:
                    return L
            mid = L+(R-L)//2
            if check(mid)<m:
                R = mid-1
            else:
                L = mid
            # print (L, R)
        return L

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # Binary search solution.
        # https://leetcode.com/problems/magnetic-force-between-two-balls/discuss/794070/Python-Binary-search-solution-with-explanation-and-similar-questions
        
        position.sort()
        
        def num_balls_placed(tested_distance):
            num_placed, current = 1, position[0]
            
            for i in range(1, len(position)):
                if position[i] - current >= tested_distance:
                    current = position[i]
                    num_placed += 1
            
            return num_placed
        
        low, high = 0, position[-1] - position[0]
        best = -1
        
        while low <= high:
            mid = (low + high) // 2
            
            if num_balls_placed(mid) < m:
                high = mid - 1
            else:
                best = mid
                low = mid + 1
                
        return best

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        maxrange = position[-1] - position[0]
        # print(maxrange)
        l, r = 1, maxrange
        while l <= r:
            mid = l + (r - l) // 2
            cnt = self.count(position, mid)
            if cnt >= m:
                l = mid + 1
            else:
                r = mid - 1
        return r
        
    def count(self, poss: list, dist: int) -> int:
        res = 1
        last = poss[0]
        for i in range(1, len(poss)):
            if poss[i] - last >= dist:
                res += 1
                last = poss[i]
        return res

class Solution:
    
    def allow(self, mid, position, m):
        #check if the given distance is possible
        #greedy approach: putting each ball in the first place
        balls = 1
        last = position[0]
        for i in range(1, len(position)):
            if(position[i] - last >= mid):
                balls+=1
                last = position[i]
        return balls>=m
    
    def maxDistance(self, position: List[int], m: int) -> int:
        o = Solution()
        #binary search
        position.sort()
        low = 0
        high = 1000000000
        pos = 0
        while(low<=high):
            mid = int((high+low)/2)
            if(o.allow(mid, position, m)):
                low = mid+1
                pos = mid
            else:
                high = mid-1
        return pos

class Solution:
    def maxDistance(self, p: List[int], m: int) -> int:
        def isFeasible(mid, arr, n, k): 
            pos = arr[0] 
            elements = 1
            for i in range(1, n): 
                if (arr[i] - pos >= mid):
                    pos = arr[i] 
                    elements += 1
                    if (elements == k): 
                        return True
            return False

        p.sort()
        #[1,2,3,4,5,100000]
        #Cm(n)
        n = len(p) 
        res = -1
        left = 0
        right = p[n - 1]
  
        while left < right: 
            mid = (left + right) // 2
            if (isFeasible(mid, p, n, m)): 
                res = max(res, mid) 
                left = mid + 1
            else: 
                right = mid 
  
        return res
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def count(d):
            answer, curr = 1, position[0]
            for i in range(1,n):
                if position[i] - curr >= d:
                    answer+=1
                    curr = position[i]
            return answer
        left, right = 0, position[-1] - position[0]
        while left < right :
            mid = right - (right- left)//2
            if count(mid) >= m :
                left = mid
            else:
                right = mid - 1
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # position = sorted(position)
        # def enough(distance):
        #     cur = position[0]
        #     c = 1
        #     for i in range(len(position)):
        #         if position[i] >= cur + distance:
        #             cur = position[i]
        #             c += 1
        #     return c>=m
        # cur_max = position[-1]-position[0] + 1
        # cur_min = 1
        # while abs(cur_min-cur_max)>1:
        #     mid = cur_min + (cur_max-cur_min)//2
        #     if enough(mid):
        #         cur_min = mid
        #     else:
        #         cur_max = mid
        # return cur_min
    
        position = sorted(position)
        n = len(position)
        if n == 2:
            return position[-1]-position[0]
        
        cur_min = 1
        cur_max = position[-1]-position[0]+1
        
        def enough(distance):
            ini = position[0]
            c = 1
            for i in range(1, n):
                if position[i]-ini >= distance:
                    ini = position[i]
                    c += 1
                
            return c>=m
            
        while(abs(cur_max-cur_min)>1):
            mid = (cur_max+cur_min)//2
            if enough(mid):
                cur_min = mid
            else:
                cur_max = mid
        
        return cur_min


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
            


            



class Solution:
    def isPossible(self, position , m , force):
        lastKept = position[0]
        m -= 1
        for i in range(1,len(position)):
            currentPosition = position[i]
            if currentPosition - lastKept >= force:
                lastKept = currentPosition
                m -= 1
        return m <= 0
            
            
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left , right = 1, 10 ** 9 + 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if self.isPossible(position,m,mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        return result


class Solution:
    def distribute(self, position, m, dist):
        prev = position[0]
        m -= 1
        for i in range(1, len(position)):
            if position[i]-prev >= dist:
                prev = position[i]
                m -= 1
            if m==0:
                return True
        return False
            
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        low, high = 0, position[-1]-position[0]
        res = 0
        while low <= high:
            mid = (high-low)//2 + low
            if self.distribute(position, m, mid):
                res = mid
                low = mid + 1
            else:
                high = mid - 1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo, hi = 0, position[-1] - position[0]
        
        def possible(target, m):
            idx = prev = 0            
            while m:
                if idx >= len(position):
                    return False
                if not prev or position[idx] >= prev + target:
                    m -= 1
                    prev = position[idx]
                else:
                    idx += 1
            return True
                
        
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if possible(mid, m):
                lo = mid
            else:
                hi = mid - 1
        
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def count(d):
            c = position[0]
            res = 1
            for n in position[1:]:
                if n-c>=d:
                    res += 1
                    c = n
            return res
        
        l = 1
        r = (position[-1] - position[0])//(m-1)
        while l <= r:
            mid = (l+r)//2
            if count(mid) < m:
                r = mid - 1
            elif count(mid+1)<m: 
                return mid
            else:
                l = mid +1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        arr = sorted(position)
        
        if m == 2:
            return arr[-1] - arr[0]
        
        def is_possible(f):
            count = 1
            origin = arr[0]
            for i in range(1, n):
                if arr[i] - origin >= f:
                    count += 1
                    origin = arr[i]
                if count >= m:
                    return True
            
            if count < m - 1 or arr[-1] - origin < f:
                return False
            
            return True
        
        low, high = 1, arr[-1] - arr[0]
        
        while low + 1 < high:
            f = ceil((high + low) / 2)
            if is_possible(f):
                low = f
            else:
                high = f

        if is_possible(high):
            return high
        return low


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(f):
            nonlocal position
            nonlocal m
            nonlocal res
            for i in range(len(position)):
                balls_cnt = 1 
                last_ball_pos = 0

                for i in range(1, len(position)):
                    last_ball_val_pos = position[last_ball_pos]
                    curr_ball_val_pos = position[i]
                    cur_force = curr_ball_val_pos - last_ball_val_pos
                    if cur_force >= f:
                        balls_cnt +=1
                        last_ball_pos = i
                        if balls_cnt == m:  
                            res = max(res, f)                      
                            return True

                return False


        res = 0
        position.sort()
        left = 1
        right = max(position)

        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                # add to answer, check if can do better increase mid and look up in right part
                left = mid + 1
            else:
                right = mid

        return res   
      


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def check(position,m,f):
            
            prev=0
            balls=1
            index=1
            
            while index<len(position) and balls<=m:
                if position[index]-position[prev]>=f:
                    prev=index
                    index+=1
                    balls+=1
                else:
                    index+=1
            
            if balls>=m:
                return True
            else:
                return False
            
        position=sorted(position)
        start=1
        end=max(position)
        
        
        while start<end:
            mid=(start+end)//2
            
            if check(position,m,mid):
                start=mid+1
            else:
                end=mid
        
        return start-1

class Solution:
    def feasible(self, d, m):
        last_pos = self.position[0]
        i = 1
        num_placed = 1
        while num_placed < m and i < self.plen:
            if self.position[i] - last_pos >= d:
                last_pos = self.position[i]
                num_placed += 1
            i += 1
        return num_placed == m

    def maxDistance(self, position: List[int], m: int) -> int:
        self.position = position
        self.plen = len(self.position)
        self.position.sort()
        left = 1
        right = self.position[-1] - self.position[0] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if self.feasible(mid, m):
                left = mid
            else:
                right = mid
        return left

class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        n = len(pos)
        if m == 2: return pos[-1] - pos[0]
        
        def valid(k):
            count, cur = 1, pos[0]
            for p in pos[1:]:
                if p - cur >= k:
                    count += 1
                    cur = p
            return count >= m
        
        l, r = 0, pos[-1] - pos[0]
        ans = 0
        while l < r:
            mid = (l + r) // 2
            if valid(mid):
                ans = max(ans, mid) 
                l = mid + 1
            else:
                r = mid
        return ans


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        
        def isvalid(gap, m):
            j = 0
            for i in range(len(position)):
                if(position[i]-position[j]>=gap):
                    m -= 1
                    j = i
                    if m == 0:
                        return True
            return False
        
        low, high = 1, position[-1]
        sem = 0
        while(low<=high):
            mid = (high + low)//2
            if isvalid(mid, m-1):
                sem = mid
                low = mid + 1
            else:
                high = mid - 1
        
        return sem
        
        
        
        
        
        
        
            
        
        
        


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        def isfeasible(dist):
            cur = pos[0]
            n = 1
            for i in range(len(pos)):
                if pos[i] >= cur + dist:
                    cur = pos[i]
                    n += 1
            return n>=m
        ng = pos[-1] - pos[0] + 1
        ok = 1
        while abs(ok-ng)>1:
            mid = ok + (ng-ok)//2
            if isfeasible(mid):
                ok = mid
            else:
                ng = mid
        return ok

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        ## need to find the maximum minmum distance 
        ## feasibility is a function of distance
        ## need to find the last feasible solution 
        ## that is the last T 
        
        def check (dist: int) -> bool:
            
            curr = position[0]
            count = 1 
            
            for i in range (len(position)):
                
                #print(abs(position[i]-curr))
                
                if (abs(position[i]-curr)>= dist):
                    
                    curr = position[i]
                    count +=1
                    
                if(i == (len(position)-1)):
                    
                    if (count >= m):
                        return True 
                    else:
                        return False 
                    
        
        ## BS for optimal length 
        
        lo = 1
        hi = (max(position)- min(position))
        
        while (lo<hi):
            
            mid= lo + ((hi-lo+1)//2)
            #print(mid)
            
            if(check(mid)):
                
                lo = mid 
            
            else : 
                hi = mid -1 
                
        
        return (lo)
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l


def isPossible(arr, n, C, mid):
    magnet = 1
    currPosition = arr[0]
    for i in range(1, n): 
        if (arr[i] - currPosition >= mid):
            magnet += 1
            currPosition = arr[i]
            if (magnet == C):
                return True
    return False

def binarySearch(n, C, arr):
    arr.sort(reverse = False) 
    lo = 0
    hi = arr[n - 1] 
    ans = 0
    while (lo <= hi):
        mid = int((lo + hi) / 2)
        if (isPossible(arr, n, C, mid) == False): 
            hi = mid - 1
        else: 
            ans = max(ans, mid) 
            lo = mid + 1
    return ans 

class Solution:
    def maxDistance(self, arr: List[int], k: int) -> int:
        n = len(arr)
        return binarySearch(n, k, arr)


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        n = len(pos)
                
        l = 1
        r = 10 ** 9
#         def isOK(gap):
#             i = 0
#             ii = 0
#             nn = 1
#             while i < n:
#                 if pos[i] - pos[ii] >= gap:
#                     nn += 1
#                     ii = i
#                 i += 1
#             return nn >= m
        
#         while l < r:
#             mid = (l + r + 1) // 2
#             if isOK(mid):
#                 l = mid
#             else:
#                 r = mid - 1 
#         return l
    
        def isNotOK(gap):
            i = 0
            ii = 0
            nn = 1
            while i < n:
                if pos[i] - pos[ii] >= gap:
                    nn += 1
                    ii = i
                i += 1
            return nn < m
        
        # find the smallest unvalid solve then minus 1
        while l < r:
            mid = (l + r) // 2
            if isNotOK(mid):
                r = mid
            else:
                l = mid + 1
        return l - 1
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        ## need to find the maximum minmum distance 
        ## feasibility is a function of distance
        ## need to find the last feasible solution 
        ## that is the last T 
        
        def check (dist: int) -> bool:
            
            curr = position[0]
            count = 1 
            
            for i in range (len(position)):
                
                #print(abs(position[i]-curr))
                
                if (abs(position[i]-curr)>= dist):
                    
                    curr = position[i]
                    count +=1 
                
                if(i == (len(position)-1)):
                    
                    if (count >= m):
                        return True 
                    else:
                        return False 
                    
        
        ## BS for optimal length 
        
        lo = 1
        hi = (max(position)- min(position))
        
        while (lo<hi):
            
            mid= lo + ((hi-lo+1)//2)
            #print(mid)
            
            if(check(mid)):
                
                lo = mid 
            
            else : 
                hi = mid -1 
                
        
        return (lo)
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        l, r, res = 0, max(position), 0
        position.sort()
        while l < r:
            mid = l + (r - l) // 2
            i, cnt = 0, 1
            while i < len(position):
                j = i + 1
                while j < len(position):
                    if position[j] - position[i] >= mid:
                        cnt += 1
                        break
                    j += 1
                i = j
                if cnt == m:
                    break
            if cnt == m:
                l = mid + 1
                res = max(res, mid)
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left , right = 0, position[-1] - position[0]
        while left <= right:
            mid = (left + right) // 2
            count = 1
            curr = position[0]
            for x in position[1:]:
                if x - curr >= mid:
                    count += 1
                    curr = x
            if count >= m:
                left = mid + 1
            else:
                right = mid - 1
        return right

from math import floor

class Solution:
    def is_min_dis_possible(self, positions, m, min_dis):
        prev = 0
        cur = 0

        while m > 0:
            m -= 1

            while cur < len(positions) and positions[cur] - positions[prev] < min_dis:
                cur += 1

            if cur >= len(positions):
                break

            prev = cur

        return True if m == 0 else False

    def maxDistance(self, position, m):
        position_sorted = sorted(position)
        high = position_sorted[-1]
        low = 0

        while low <= high:
            mid = floor((high + low) / 2)
            if mid == low:
                break

            is_min_dis_possible = self.is_min_dis_possible(position_sorted, m, mid)
            if is_min_dis_possible:
                low = mid
            else:
                high = mid

        return low

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def possible(d):
            cnt = 1
            cur = position[0]
            for i in range(1, len(position)):
                if position[i] - cur >= d:
                    cnt += 1
                    cur = position[i]
                if cnt >= m:
                    return True
            return False
        
        lo = 0
        hi = position[-1] - position[0]
        while lo < hi:
            mid = hi - (hi - lo) // 2
            if possible(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def valid(dis):
            prev = 0
            balls = 1
            for i in range(1, n):
                if position[i] - position[prev] >= dis:
                    balls += 1
                    prev = i
            return balls >= m
        
        lo, hi = 0, position[-1] - position[0]
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if valid(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # 二分查找
        # 判断若x为最小磁力,能否分隔出m-1个间隔
        def Valid(x):
            ans = 0
            target = position[0]
            for i in range(1,len(position)):
                if position[i] - target >= x:
                    ans += 1
                    target = position[i]
            return ans >= m - 1
        position.sort()
        l,r = min(position[i + 1] - position[i] for i in range(len(position) - 1)),(position[-1] - position[0]) // (m - 1)
        while l <= r:
            mid = l + (r - l) // 2
            # 若最小磁力可以分成m-1个间隔,则可能存在更大值,否则最小磁力值应当更小
            if Valid(mid):
                l = mid+1
            else:
                r = mid - 1
        return l-1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo, hi = 0, position[-1] - position[0]
        
        def possible(target, m):
            idx = prev = 0            
            while m:
                if idx >= len(position):
                    return False
                if not prev or position[idx] >= prev + target:
                    m -= 1
                    prev = position[idx]
                else:
                    idx += 1
            return True
                
        
        while lo <= hi:
            mid = (lo + hi) >> 1
            if possible(mid, m):
                lo = mid + 1
            else:
                hi = mid - 1
        
        return lo - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def feasible(min_req_dist, b):
            i = 0
            prev_pos = None
            while i < len(position) and b > 0:
                if prev_pos == None or position[i] - prev_pos >= min_req_dist:
                    b -= 1
                    prev_pos = position[i]
                i += 1
            return b == 0
        
        position.sort()
        n = len(position)
        low = 1
        high = position[-1]
        while low < high:
            mid = (low + high) // 2 + 1
            if feasible(mid, m):
                low = mid
            else:
                high = mid - 1
        return low
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        start, end = 0, position[-1]
    
        while start + 1 < end:
            mid = (start + end) // 2
            if self.isValid(position, mid) < m:
                end = mid
            else:
                start = mid
                
        if self.isValid(position, end) < m:
            return start
        else:
            return end
        
        
    def isValid(self, position, dist):
        cnt = 1
        i = 1
        current = position[0] + dist
        while i < len(position):
            if position[i] >= current:
                cnt += 1
                current = position[i] + dist
            i += 1
        return cnt
        
            



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def feasible(d, position):
            # print(\"Check d: \", d)
            balls = [position[0]]
            placed = 1
            i = 1
            while i <= len(position) - 1:
                if position[i] - balls[-1] >= d:
                    balls.append(position[i])
                    # print(balls)
                    placed += 1
                    if placed == m:
                        return True
                i += 1 
            return False
        
        position.sort()
        
        left, right = 1, max(position)
                
        while left < right:
            mid = right - (right - left) // 2
            if feasible(mid, position):
                left = mid 
            else:
                right = mid - 1
        return left

class Solution:
    def isSolution(self, m, position, minforce):
        index = 0
        remaining = m
        for bin in position:
            if bin >= index:
                remaining-=1
                index = bin + minforce
            if remaining == 0:
                return True
        return False
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        maxDist = position[-1]
        minDist = 0
        while maxDist > minDist + 1:
            average = (minDist + maxDist) // 2
            #print (\"average \", average)
            if Solution.isSolution (self, m, position, average):
                #print (\"is Sol\")
                minDist = average
            else:
                maxDist = average  
                #print (\"not Sol\")
        if Solution.isSolution (self, m, position, maxDist):
            return maxDist
        else:
            return minDist
            
            
             
            
            


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        n = len(pos)
#         def check(gap):
#             i = 0
#             ii = 0
#             nn = 1
#             while i < n:
#                 if pos[i] - pos[ii] >= gap:
#                     nn += 1
#                     ii = i
#                 i += 1
#             return nn >= m
        
#         l = 1
#         r = 10 ** 9
        
#         while l < r:
#             mid = (l + r + 1) // 2
#             if check(mid):
#                 l = mid
#             else:
#                 r = mid - 1 
#         return l
    
        def isNotOK(gap):
            i = 0
            ii = 0
            nn = 1
            while i < n:
                if pos[i] - pos[ii] >= gap:
                    nn += 1
                    ii = i
                i += 1
            return nn < m
        
        l = 1
        r = 10 ** 9
        
        while l < r:
            mid = (l + r) // 2
            if isNotOK(mid):
                r = mid
            else:
                l = mid + 1 
        return l - 1
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        
        def check(min_force):
            count = 1
            k = position[0]
            for n in position:
                if n-k >= min_force:
                    count += 1
                    k = n
                    if count >= m:
                        return True
            return False
        
        
        i, j = 1, position[-1]-position[0]
        while i <= j:
            mid = (i+j)//2
            c1 = check(mid)
            c2 = check(mid+1)
            if c1 and not c2:
                return mid
            if not c1:
                j = mid-1
            else:
                i = mid+1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 0, position[-1] - position[0] + 1
        
        def c(x):
            y = m
            y -= 1
            last = 0
            j = 0
            for _ in range(y):
                while j < len(position) and position[j] - position[last] < x:
                    j += 1
                if j == len(position):
                    # print(j, last, x)
                    return 0
                last = j
            return 1
        
        while l < r:
            mid = (r+l)//2
            dist = c(mid)
            # print('len', mid, l, r, dist)
            if not dist:
                r = mid
            else:
                l = mid+1
        return l-1

class Solution:
    
        
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def f(mid,position,m):
            f=position[0]
            m=m-1
            for j in range(1,len(position)):
                if position[j]-f>=mid:
                    f=position[j]
                    m=m-1
                if m<0:
                    break
            if m<=0:
                return True
            return False
        h=(position[-1]-position[0])//(m-1)+1
        l=0
        while h>=l:
            mid=(h+l)//2
            
            print(mid)
            if f(mid,position,m):
                l=mid+1
            else:
                h=mid-1
        return l-1

class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        
        positions.sort()
               
        def possible(positions,m,v):
            
            cur=0
            for i in range(1,len(positions)):
                if positions[i]-positions[cur]>=v:
                    m-=1
                    cur=i
                    if m==1: return True            
            return m<=1

        
        left,right=1,positions[-1]-positions[0]
        ans=0
        while left<=right:
            
            v=(left+right)//2
            if possible(positions,m,v):
                ans=v
                left=v+1
            else:
                right=v-1
        
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        high=position[-1]-position[0]
        low = high
        for i in range(1, len(position)):
            low = min(low, position[i]-position[i-1])
        
        def feasible(force):
            last = position[0]
            count=1
            for i in range(1,len(position)):
                if (position[i]-last)>=force:
                    last=position[i]
                    count+=1
            if count >= m:
                return True
            return False
        
        while low < high:
            mid = (low+high)//2
            if not feasible(mid):
                high=mid
            else:
                low=mid+1
        low-=1
        ans=float('inf')
        last=position[0]
        for i in range(1, len(position)):
            if (position[i]-last)>=low:
                ans=min(ans, position[i]-last)
                last=position[i]
        
        return ans
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        n = len(position)
        position.sort()

        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans

        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1

        print(l)
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def valid_distance(d):
            cur, idx, total = 0, 1, 1
            
            while idx < len(position) and total < m:
                if position[idx] - position[cur] >= d:
                    total += 1
                    cur = idx
                idx += 1
            return total == m
        
        position.sort()
        s, e= 0, position[-1] - position[0] + 1
        
        while s < e:
            mid = s + (e - s) // 2
            if valid_distance(mid):
                s = mid + 1
            else:
                e = mid
        return s - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def isfail(mid):
            ans = 1
            curr = position[0] # alike greedy idea, we just put the first ball at position 0!
            for i in range(1, n):
                if position[i] - curr >= mid:
                    ans += 1
                    curr = position[i]
            return ans < m
        
        left = 0 
        right = max(position) - min(position) + 1
        while left < right:
            mid = (left+right)//2
            if isfail(mid):
                right = mid
            else:
                left = mid + 1
        return left - 1 # left is the min value to fail, so left-1 is the max value to succeed!
        # 因为求的是最大值！所以需要巧妙使用binary search!


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position = sorted(position)
        lo = 1
        hi = position[-1]-position[0]
        
        while lo<hi:
            
            mid = (lo+hi+1)//2
            
            # count number of balls that can be placed if distance at least mid
            ind1 = 0
            ind2 = 1
            count = 1
            while ind2<len(position) and count<m:
                
                if position[ind2]-position[ind1]>=mid:
                    count += 1
                    ind1 = ind2
                    
                ind2 += 1
                
            if count>=m:
                lo = mid
            else:
                hi = mid-1
        
        return lo

from functools import lru_cache
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        
        def can_place(mid): # mid is candidate for minimum magnetic force
            num_placed = 1
            prev = position[0]
            
            for num in position[1:]:
                if num - prev >= mid:
                    num_placed += 1
                    prev = num

            return num_placed >= m  
        
        left = 0
        right = position[-1] - position[0]
        
        res = 0
        while left < right:
            mid = (left + right) // 2

            if can_place(mid):
                left = mid + 1
            else:
                right = mid
        
        return left - 1
        
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def feasible(min_req_dist, b):
            i = 0
            prev_pos = None
            while i < len(position) and b > 0:
                if prev_pos == None or position[i] - prev_pos >= min_req_dist:
                    b -= 1
                    prev_pos = position[i]
                i += 1
            return b == 0
        
        # This is a fantastic example of establishing a monotonic predicate and 
        # squeeze from the right side of the search space (instead of the usual left-side)
        position.sort()
        low = 1
        high = position[-1]
        while low < high:
            # Since we constantly trying to see if we could find a feasible solution that's
            # greater than the current one, we want to always make progress by advancing
            # mid to the right. (low + high) // 2 + 1 guarantees this, even when we have
            # just two elements. mid will be pointing at high. Otherwise we'd get an infinite
            # loop with (low + high) // 2
            mid = (low + high) // 2 + 1
            if feasible(mid, m):
                low = mid
            else:
                high = mid - 1
        return low
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def distributable(n):
            pos = len(position) - 1
            balls = m
            while pos >= 0 and balls:
                balls -= 1
                np = position[pos] - n
                while pos >= 0 and position[pos] > np:
                    pos -= 1
            return not balls       
        position = sorted(position)
        lo, hi = 1, (position[-1] - position[0]) // (m -1) + 1
        ans = lo
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans 

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def trial(n):
            prev, curr, ct = 0, 1, 1
            while True:
                if curr >= len(position):
                    return False
                if position[curr] - position[prev] >= n:
                    prev = curr
                    ct += 1
                if ct == m:
                    return True
                curr += 1
        
        l, r = 1, position[-1] - position[0] + 1
        ret = 0
        while l < r:
            mid = (l + r) // 2
            ans = trial(mid)
            if ans:
                l = mid + 1
            else:
                r = mid
        return r - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        
        def ispossible(f: int) -> bool:
            Count, pos = 1, 0
            
            for i in range(1, len(position)):
                
                if position[i]  - position[pos] >= f:
                    pos = i
                    Count += 1
                    
            return bool(Count >= m)
        
        start, end = 1, position[-1] - position[0]
        
        while start < end:
            
            mid = (start + end)//2
            if ispossible(mid) and not ispossible(mid + 1): return mid
            elif ispossible(mid): start = mid + 1
            else: end = mid - 1
                
        return start
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        @lru_cache(None)
        def helper(gap):
            prev = 0
            cnt = 1
            while cnt < m:
                idx = prev + 1
                while idx < len(position) and position[idx] - position[prev] < gap:
                    idx += 1
                if idx >= len(position): break    
                prev = idx
                cnt += 1
            return cnt == m
        
        lb, ub = 1, position[-1] - position[0] + 1
        while lb < ub:
            mid = lb + (ub - lb)//2
            if helper(mid):
                if not helper(mid + 1): return mid
                else: lb = mid + 1
            else: ub = mid
                
        return lb

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        high = position[-1] - position[0]
        low = 1
        while high != low:
            mid = (high + low + 1) // 2
            balls = 1
            start = position[0]
            for i in range(1, n):
                if position[i] - start >= mid:
                    balls += 1
                    start = position[i]
            if balls >= m:
                low = mid
            else:
                high = mid - 1
        return low
            
            

            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        left, right = 1, (position[-1]-position[0])//(m-1) + 2 
        while left < right:
            mid = left + (right-left)//2 + 1
            
            if self.can_use_as_min(position, mid, m):
                left = mid
            else:
                right = mid-1
            
        return left    
    
    def can_use_as_min(self, position, min_distance, m):
        m -= 1
        i = 1    
        last_position = position[0] 
        
        while m > 0:
            while position[i] - last_position < min_distance:
                i += 1
                
                if i >= len(position):
                    return False
                
            last_position = position[i]    
            m -= 1
        
        return True 

import bisect

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        pos = sorted(position)
        if m == 2:
            return pos[-1] - pos[0]
        
        def isFeasible(d):
            j = 0
            for k in range(1, m):
                j = bisect.bisect_left(pos, pos[j] + d, j + 1)
                if j == n:
                    return False
            return True
        
        res = -1
        lo, hi = 1, pos[-1] - pos[0] + 1
        while lo < hi: 
            d = (lo + hi) // 2
            print(lo, hi, d)
            if isFeasible(d):
                lo = d + 1
            else: 
                hi = d
        return hi - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r, sol = 0, position[-1] - position[0], -1
        
        def helper(target):
            pre, cnt = position[0], 1
            
            for n in position:
                temp = n - pre
                
                if temp >= target: 
                    cnt += 1
                    pre = n                    
                                                            
            if (position[-1] - pre) >= target: cnt += 1
                
            if cnt >= m: return True
            
            return False
            
        while l <= r:
            mid = (l + r) // 2
            
            if (helper(mid)):
                l = mid + 1
                
            else:
                r = mid - 1
                
        return l - 1
            
            
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        L = len(position)
        
        left = 1
        right = position[-1]-position[0]
        
        def can_place(f):
            n_ball = m-1
            cum_dis = 0
            p = 1
            #n_ball -= 1
            while n_ball >0 and p<L :
                cum_dis += position[p]-position[p-1]
                if cum_dis >= f:
                    n_ball -= 1
                    cum_dis = 0
                p += 1
            
            if n_ball == 0:
                return True
            else:
                return False
                    
                
        #return can_place(4)
        # 1, 9, 5 false
        # 1, 4, 2, true
        # 2, 4, 3, true
        # 3, 4, 3,
        
        while left < right:
            mid = (left+right)//2
            if can_place(mid):
                left = mid
            else:
                right = mid-1
            if right-left == 1:
                if can_place(right):
                    return right
                else:
                    return left

        
        #return can_place(3)
        return left
            
#         if m == 2:
#             return position[-1] - position[0]
        
#         L = len(position)
        
#         hp = []
#         f_set = {}
#         b_set = {}
#         for i in range(L-1):
#             heapq.heappush(hp, (position[i+1]-position[i], position[i], position[i+1]))
#             f_set[position[i]] = position[i+1]
#             b_set[position[i+1]] = position[i]
        
#         total = L-1
        
#         while total > m-1:
#             l, x, y = heapq.heappop(hp)
#             if x in f_set and y in b_set and f_set[x] == y and b_set[y] == x:
#                 left_len = float(inf)
#                 right_len = float(inf)
#                 if y in f_set:
#                     right_len = f_set[y]-y
#                 if x in b_set:
#                     left_len = x-b_set[x]
#                 if left_len < right_len:
#                     #merge with left
#                     new_y = y
#                     new_x = b_set[x]
#                     del f_set[x]
#                     del b_set[x]
#                     f_set[new_x] = new_y
#                     b_set[new_y] = new_x
#                     ret = new_y - new_x
#                 else:
#                     # merge with right
#                     new_y = f_set[y]
#                     new_x = x
#                     del f_set[y]
#                     del b_set[y]
#                     f_set[new_x] = new_y
#                     b_set[new_y] = new_x
#                     ret = new_y - new_x
#                 heapq.heappush(hp, (new_y-new_x, new_x, new_y))
#                 total -= 1
        
#         ret = float(inf)
#         for k in f_set.keys():
#             ret = min(ret, f_set[k]-k)
        
#         return f_set
                         
            
        
        
            


class Solution:
    def maxDistance(self, A, m: int) -> int:
        
        
        A.sort()
        
        def test(mid):
            cnt = m - 1
            cur = A[0]
            for i in A[1:]:
                if i - cur >= mid:
                    cnt -= 1
                    cur = i
                else:
                    continue
                if cnt == 0: return True
            return False
        
        mi = 1
        ma = (A[-1] - A[0]) // (m - 1)
        while mi <= ma:
            mid = (mi + ma) // 2
            if test(mid):
                mi = mid + 1
            else:
                ma = mid - 1
        return ma

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        minp, maxp = position[0], position[-1]
        lo, hi = 1, (maxp - minp) // (m -1) + 1
        ans = lo
        def distributable(n):
            pos = position.copy()
            balls = m
            while pos and balls:
                balls -= 1
                np = pos[-1] - n
                while pos and pos[-1] > np:
                    pos.pop()
            return not balls       
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans        

class Solution:
    def maxDistance(self, position: List[int], cuts: int) -> int:
        position = sorted(position)
        l, r = 1, position[-1] - position[0]
        while l != r:
            m = (l + r) // 2 + 1
            if self.isValid(position, m, cuts):
                l = m
            else:
                r = m - 1
        return l

    def isValid(self, position, force, cuts):
        c = 0
        l = 0
        for r in range(1, len(position)):
            if position[r] - position[l] >= force:
                c += 1
                l = r
        return c >= cuts-1

class Solution:
    def maxDistance(self, p: List[int], m: int) -> int:
        n=len(p)
        p.sort()
        def check(x):
            st=p[0]
            cnt=1
            for i in range(1,n):
                if abs(p[i]-st)>=x:
                    st=p[i]
                    cnt+=1 
            return cnt>=m
        lo=1
        hi=max(p)+4
        print(check(999999999))
        while lo<=hi:
            mi=(lo+hi)//2
            if check(mi):
                ans=mi 
                lo=mi+1 
            else:
                hi=mi-1 
            #print(mi,check(mi))
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # binary search
        def isValid(f, k):
            # return true if it is possible to arrange m elements in array such that minimum distance is f
            pos = position[0]
            count = 1
            for i in range(1, n):
                if (position[i] - pos >= f):
                    # put it here
                    pos = position[i]
                    count += 1
                    
                    if count == k:
                        return True
                    
            return False
        
        n = len(position)
        position.sort()
        res = 0
        
        l, r = 0, position[n-1] - position[0] + 1
        while l < r:
            mid = (l+r) >> 1
            if isValid(mid, m):
                res = max(res, mid)
                l = mid + 1
                
            else:
                r = mid
                
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        ## need to find the maximum minmum distance 
        ## feasibility is a function of distance
        ## need to find the last feasible solution 
        ## that is the last T 
        
        def check (dist: int) -> bool:
            
            curr = position[0]
            count = 1 
            
            for i in range (len(position)):
                
                #print(abs(position[i]-curr))
                
                if (abs(position[i]-curr)>= dist):
                    
                    curr = position[i]
                    count +=1 
                    
                    if (count>=m):
                        return True 
                    
                    
                if(i == (len(position)-1)):
                    
                    if (count >= m):
                        return True 
                    else:
                        return False 
                    
        
        ## BS for optimal length 
        
        lo = 1
        hi = (max(position)- min(position))
        
        while (lo<hi):
            
            mid= lo + ((hi-lo+1)//2)
            #print(mid)
            
            if(check(mid)):
                
                lo = mid 
            
            else : 
                hi = mid -1 
                
        
        return (lo)
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def possible(mid):
            temp = m-1
            prev = position[0]
            for i in range(len(position)):
                if(position[i] - prev>=mid):
                    prev = position[i]
                    temp-=1
            return(temp<=0)
        l,r = 0,max(position)
        position.sort()
        while(l<r):
            mid = (l+r)//2
            print((l,mid,r))
            if(r == l+1):
                if(possible(r)):
                    l = r
                else:
                    r = l
                break
            if(possible(mid)):
                l = mid
            else:
                r = mid - 1
        return(l)
        


class Solution:
    def maxDistance(self, arr: List[int], m: int) -> int:
        arr.sort()
        
        def isFeasible(mid): 
            pos = arr[0] 

            # Initialize count of elements placed. 
            elements = 1

            # Try placing k elements with minimum 
            # distance mid. 
            for i in range(1, len(arr)): 
                if (arr[i] - pos >= mid): 

                    # Place next element if its distance  
                    # from the previously placed element 
                    # is greater than current mid 
                    pos = arr[i] 
                    elements += 1

                    # Return if all elements are placed 
                    # successfully 
                    if (elements == m): 
                        return True
            return 0
  
        
        hi = arr[-1] - arr[0]
        lo = float('inf')
        for i in range(len(arr)-1):
            lo = min(lo, arr[i+1]-arr[i])
        
        ans = float('-inf')
        
        while lo<=hi:
            mid = (lo+hi)//2
            if isFeasible(mid):
                ans = max(ans, mid)
                lo = mid+1
            else:
                hi = mid-1
        
        return ans
    
    
    
                
   
        
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def maxNumberBallsCanBePlaced(minDis):
            count = 1
            end = position[0]
            for i in range(len(position)):
                if(position[i] - end >= minDis):
                    end = position[i]
                    count += 1
            return count
        
        position.sort()
        left = 1
        right = position[-1]
        while(left < right):
            mid = left + (right - left) // 2
            
            if(maxNumberBallsCanBePlaced(mid) >= m):
                left = mid + 1
            else:
                right = mid
        
        return left - 1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        size = len(position)
        
        # --------------------------------------------
        def satisfy( gap ) -> bool:
            '''
            input: gap
            output: True, if m balls can be placed with distance >= gap.
                    False, otherwise.
            '''
            
            next_valid_pos = position[0] + gap
            
            # start from smallest position
            good_positions = 1
            
            for idx in range(1, size):
                
                if position[idx] >= next_valid_pos:
                    good_positions += 1
                    next_valid_pos = position[idx] + gap
                
                if good_positions == m:
                    return True
            
            return False
        
        # --------------------------------------------
        
        # preprocessing, keep it sorted in ascending order
        position.sort()
        
        # maximum gap between two balls
        max_gap = (position[-1] - position[0]) // (m - 1)
        
        # minimum gap between two balls
        min_gap = min( position[i] - position[i-1] for i in range(1, size) )
        
        
        
        if m == 2:
            
            # Quick response for simple case
            return max_gap
        
        
        
        # launch binary search to find optimal gap
        left, right = min_gap, max_gap
        
        while left <= right:
            
            gap_trial = left + (right - left) // 2
            
            if satisfy(gap=gap_trial):
                
                # m balls can be placed with gap_trial
                # make gap_trial larger, and try again
                left = gap_trial + 1
                
            else:

                # m balls cannot be placed with gap_trial
                # make it smaller, and try again
                right = gap_trial - 1
        
        
        # because left = gap_trial + 1
        # left - 1 is the optimal gap
        return left-1
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def valid(dis):
            count = 1
            prev = position[0]
            for n in position:
                if n-prev >= dis:
                    count += 1
                    prev = n
                if count == m: return True
            return False
        
        l, r = 0, position[-1]
        ret = 0
        # print(position, l, r)
        while l < r:
            mid = l + (r-l)//2
            # print(l, r, mid)
            if valid(mid):
                ret = max(ret, mid)
                l = mid+1
            else:
                r = mid
        return ret

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def trial(n):
            prev, curr, ct = 0, 1, 1
            while True:
                if curr >= len(position):
                    return False
                if position[curr] - position[prev] >= n:
                    prev = curr
                    ct += 1
                if ct == m:
                    return True
                curr += 1
        
        l, r = 1, position[-1] - position[0] + 1
        ret = 0
        while l < r:
            mid = (l + r + 1) // 2
            ans = trial(mid)
            if ans:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position.sort()
        L = len(position)
        
        left = 1
        right = position[-1]-position[0]
        
        def can_place(f):
            n_ball = m-1
            cum_dis = 0
            p = 1
            #n_ball -= 1
            while n_ball >0 and p<L :
                cum_dis += position[p]-position[p-1]
                if cum_dis >= f:
                    n_ball -= 1
                    cum_dis = 0
                p += 1
            
            if n_ball == 0:
                return True
            else:
                return False
                    
                
        #return can_place(4)
        # 1, 9, 5 false
        # 1, 4, 2, true
        # 2, 4, 3, true
        # 3, 4, 3,
        
        while left < right:
            mid = right- (-left+right)//2
            #mid = (left+right)//2
            if can_place(mid):
                left = mid
            else:
                right = mid-1
            # if right-left == 1:
            #     if can_place(right):
            #         return right
            #     else:
            #         return left

        
        #return can_place(3)
        return left
            
#         if m == 2:
#             return position[-1] - position[0]
        
#         L = len(position)
        
#         hp = []
#         f_set = {}
#         b_set = {}
#         for i in range(L-1):
#             heapq.heappush(hp, (position[i+1]-position[i], position[i], position[i+1]))
#             f_set[position[i]] = position[i+1]
#             b_set[position[i+1]] = position[i]
        
#         total = L-1
        
#         while total > m-1:
#             l, x, y = heapq.heappop(hp)
#             if x in f_set and y in b_set and f_set[x] == y and b_set[y] == x:
#                 left_len = float(inf)
#                 right_len = float(inf)
#                 if y in f_set:
#                     right_len = f_set[y]-y
#                 if x in b_set:
#                     left_len = x-b_set[x]
#                 if left_len < right_len:
#                     #merge with left
#                     new_y = y
#                     new_x = b_set[x]
#                     del f_set[x]
#                     del b_set[x]
#                     f_set[new_x] = new_y
#                     b_set[new_y] = new_x
#                     ret = new_y - new_x
#                 else:
#                     # merge with right
#                     new_y = f_set[y]
#                     new_x = x
#                     del f_set[y]
#                     del b_set[y]
#                     f_set[new_x] = new_y
#                     b_set[new_y] = new_x
#                     ret = new_y - new_x
#                 heapq.heappush(hp, (new_y-new_x, new_x, new_y))
#                 total -= 1
        
#         ret = float(inf)
#         for k in f_set.keys():
#             ret = min(ret, f_set[k]-k)
        
#         return f_set
                         
            
        
        
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1]-position[0]
        while l<r:
            mid = l+(r-l+1)//2
            placefind = 1
            preIndex = 0
            for i in range(1, len(position)):
                if position[i]-position[preIndex]>=mid:
                    placefind += 1
                    preIndex = i
            if placefind >= m:
                l = mid
            else:
                r = mid-1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo=0   
        hi=position[-1]-position[0]
        n=len(position)
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
                    
            
        while lo<hi:
            mid= (lo+hi+1)//2
            res=count(mid)
            if res>=m:
                lo=mid
            elif res<m:
                hi=mid-1
        return lo
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:

        def check(space):
            count = start = 0
            for i in range(1, len(position)):
                if position[i] - position[start] >= space:
                    count += 1
                    start = i
            print(space, count)
            return count >= m - 1

        def find_space(lo, hi):
            while lo < hi:
                mid = int((lo / 2) + (hi / 2))
                if check(mid) and not check(mid + 1):
                    return mid
                if check(mid):
                    lo = max(mid, lo + 1)
                else:
                    hi = mid
            hi -= 1
            while check(hi):
                hi += 1
            return hi - 1

        position.sort()
        return find_space(1, position[-1] - position[0])

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, 10**9
        while l < r:
            mid = (l+r+1)//2
            count = 1
            prev = position[0]
            for i in range(1, len(position)):
                if position[i] - prev >= mid:
                    count += 1
                    prev = position[i]
            
            
            if count >= m :
                l = mid
            else:
                r = mid-1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def is_feasible(force):
            count = 1
            cur = position[0]
            for i in range(1, n):
                # print(position[i], cur)
                if position[i] - cur >= force:
                    count += 1
                    cur = position[i]
            return count >= m
        
        l = 1
        r = position[-1] - position [0] + 1
        while l < r:
            med = (l + r) // 2
            if is_feasible(med):
                l = med + 1
            else:
                r = med
        return l - 1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # 二分查找
        # 判断若x为最小磁力,能否分隔出m-1个间隔
        def Valid(x):
            ans = 0
            target = position[0]
            for i in range(1,len(position)):
                if position[i] - target >= x:
                    ans += 1
                    target = position[i]
            return ans >= m - 1
        position.sort()
        l,r = min(position[i + 1] - position[i] for i in range(len(position) - 1)),(position[-1] - position[0]) // (m - 1)
        while l <= r:
            mid = l + (r - l) // 2
            # 若最小磁力可以分成m-1个间隔,则可能存在更大值,否则最小磁力值应当更小
            if Valid(mid):
                l = mid+1
            else:
                r = mid-1
        return l-1


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def realizable(value):
            last = position[0]
            placed = 1
            for k in range(1, len(position)):
                if position[k] - last >= value:
                    placed += 1
                    last = position[k]
            return placed >= m
        
        min_dist, max_dist = position[1] - position[0], position[-1] - position[0]
        for k in range(1,len(position)):
            min_dist = min(min_dist, position[k]-position[k-1])
        
        left, right = min_dist, max_dist + 1
        print(left, right)
        while left < right:
            mid = left + (right - left) // 2
            if not realizable(mid):
                right = mid
            else:
                left = mid + 1
        return left - 1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check_force(position, pivot, m):
            anchor = position[0]
            cnt = 1
            for i in range(1, len(position)):
                if position[i] - anchor >= pivot:
                    anchor = position[i]
                    cnt += 1
                    
                    if cnt == m:
                        #print(\"Successfully placed all baskets\")
                        return True
            return False
                
        position = sorted(position)
        low, high = 0, position[-1]       
        output = -1
        
        # Standard binary search recipe
        while low < high:
            pivot = (low + high) // 2
            if check_force(position, pivot, m):
                output = max(output, pivot)
                low = pivot + 1
            else:
                high = pivot        
        return output

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:

        def check(space):
            count = start = 0
            for i in range(1, len(position)):
                if position[i] - position[start] >= space:
                    count += 1
                    start = i
#            print(space, count)
            return count >= m - 1

        def find_space(lo, hi):
            while lo < hi:
                mid = int((lo / 2) + (hi / 2))
                if check(mid) and not check(mid + 1):
                    return mid
                if check(mid):
                    lo = max(mid, lo + 1)
                else:
                    hi = mid
            hi -= 1
            while check(hi):
                hi += 1
            return hi - 1

        position.sort()
        return find_space(1, position[-1] - position[0])

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        # print('------------')
        maxVal = position[-1] - position[0]
        answer = 0
        
        low, high = 1, maxVal
        
        def isValid(mid):
            pos = position[0]
            elements = 1
            for i in range(1, len(position)): 
                if (position[i] - pos >= mid): 
                    pos = position[i] 
                    elements += 1
                    if (elements == m): 
                        return True
            return False

        while low <= high:
            mid = (low+high)//2
            # print(mid)
            if isValid(mid):
                answer = max(answer, mid)
                low = mid + 1
            else:
                high = mid - 1
                
        return answer

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        mid = max(position) // 2
        gap = max(1,mid//2)
        
        t = 0
        best = 0
        
        while True:
            c = 1
            last = position[0]
            for i in range(1,len(position)):
                if position[i] - mid >= last:
                    c+=1
                    last = position[i]
                    
            
                    
            if c>=m:
                best = max(best,mid)
                mid = mid + gap
                
                
            else:
                mid = mid - gap
                
            gap = gap//2
            gap = max(1,gap)
            t+=1
            
            if t==50:
                break
                
        return (best)
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def isPossible(arr, n, C, mid): 
            # Variable magnet will store count of 
            # magnets that got placed and 
            # currPosition will store the position 
            # of last placed magnet 
            magnet = 1
            currPosition = arr[0] 

            for i in range(1, n): 

                # If difference between current index 
                # and last placed index is greater than 
                # or equal to mid it will allow placing 
                # magnet to this index 
                if (arr[i] - currPosition >= mid): 
                    magnet += 1

                    # Now this index will become 
                    # last placed index 
                    currPosition = arr[i] 

                    # If count of magnets placed becomes C 
                    if (magnet == C): 
                        return True

            # If count of placed magnet is 
            # less than C then return false 
            return False

        # Function for modified binary search 
        def binarySearch(n, C, arr): 
            # Sort the indices in ascending order 
            arr.sort(reverse = False) 

            # Minimum possible distance 
            lo = 0

            # Maximum possible distance 
            hi = arr[n - 1] 
            ans = 0

            # Run the loop until lo becomes 
            # greater than hi 
            while (lo <= hi): 
                mid = int((lo + hi) / 2) 

                # If not possibble, decrease value of hi 
                if (isPossible(arr, n, C, mid) == False): 
                    hi = mid - 1
                else: 

                    # Update the answer 
                    ans = max(ans, mid) 
                    lo = mid + 1

            # Return maximum possible distance 
            return ans
        
        n = len(position)
        return binarySearch(n, m, position)


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def cnt(mid) -> int:
            ans, cur = 1, position[0]
            for i in range(1, n):
                if position[i] - cur >= mid:
                    ans += 1
                    cur = position[i]
            return ans
            
        l, r = 0, position[-1] - position[0]
        while(l < r):
            mid = r - (r - l)//2
            if cnt(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
         
        def helper(position, x, m):
            prev = position[0]
            m -= 1
            #greedy
            for i in range(1, len(position)):
                if position[i] - prev>= x:
                    prev = position[i]
                    m -=1                  
                if m == 0:
                    break            
            if m == 0:
                return x
            else:
                return -1
        
        l = 1
        r = position[-1] - position[0] + 1
        ans = 0
        while l < r:
            mid = (l + r)//2
            realMinimumForce = helper(position, mid, m)
            print((mid, realMinimumForce))
            if realMinimumForce == -1:
                r = mid
            
            else:
                l = mid + 1
                ans = max(ans,realMinimumForce)
                
        
        
        
        return ans


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def isfail(mid):
            ans = 1
            curr = position[0] # alike greedy idea, we just put the first ball at position 0!
            for i in range(1, n):
                if position[i] - curr >= mid:
                    ans += 1
                    curr = position[i]
            return ans < m
        
        res = float('-inf')
        left = 1
        right = position[-1] - position[0]
        
        while left <= right:
            mid = (left+right)//2
            if isfail(mid):
                right = mid-1
            else:
                left = mid + 1
                res = max(res,mid)
        return res 

class Solution:
    def checkDistance(self, position, minDist, m):
        lastBallPos = position[0]
        ballLeft = m - 1
        i = 1
        while i < len(position) and ballLeft != 0:
            if minDist <= position[i] - lastBallPos:
                lastBallPos = position[i]
                ballLeft -= 1
            i += 1
        return ballLeft == 0
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        high = 1000000000
        low = 1
        ans = 1
        while low < high:
            middle = (high + low + 1) // 2
            if self.checkDistance(position, middle, m):
                low = middle
            else:
                high = middle - 1
        return low

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def count(d):
            prev, tot = position[0], m-1
            for i in range(1, len(position)):
                if position[i] - prev >= d:
                    prev = position[i]
                    tot -= 1
                    if tot == 0: return True
            return False
        position.sort()
        low, high = 0, position[-1]-position[0]
        res = None
        while low <= high:
            mid = (low + high)//2
            if count(mid):
                res = mid
                low = mid + 1
            else:
                high = mid - 1
        return res
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
         
        def helper(position, x, m):
            res = float('inf')
            prev = position[0]
            m -= 1
            for i in range(1, len(position)):
                if position[i] - prev>= x:
                    res = min(position[i] - prev, res)
                    prev = position[i]
                    m -=1
                    
                    
                if m == 0:
                    break
            
            if m == 0:
                return res
            else:
                return -1
                
        
        l = 1
        r = position[-1] - position[0] + 1
        ans = 0
        while l < r:
            mid = (l + r)//2
            realMinimumForce = helper(position, mid, m)
            #print(mid, realMinimumForce)
            if realMinimumForce == -1:
                r = mid
            
            else:
                l = mid + 1
                ans = max(ans,realMinimumForce)
                
        
        
        
        return ans


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo, hi = 0, position[-1] - position[0]
        def check(amt):
            curr = position[0]
            cnt = 1
            for x in position[1:]:
                if x - curr >= amt:
                    cnt += 1
                    curr = x
            return cnt >= m
        while lo < hi:
            mi = (hi + lo + 1) // 2
            if check(mi):
                lo = mi
            else:
                hi = mi-1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def validPlacement(spacing):
            placed, curPosition = 1, position[0]
            for p in position:
                if p - curPosition >= spacing:
                    placed += 1
                    curPosition = p
            return placed >= m
                
        ## IDEA: do binary search to find the minimum foracce (maximum space)
        position.sort()
        lo, hi = 0, position[-1] - position[0]
        while (lo < hi):
            mid = hi - (hi - lo) // 2 # midpoint formula to prevent integer overflow in other languages
            if validPlacement(mid):
                lo = mid
            else:
                hi = mid -1
        return lo

import bisect

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        n = len(position)
        if m == 2: return position[-1] - position[0]
        
        
        lp = 0
        rp = (position[-1] - position[0])
        
        def can(gap):
            lidx = 0
            left = m - 1
            ptr = 1
            while left > 0 and ptr < n:
                if position[ptr] - position[lidx] >= gap:
                    left -= 1
                    lidx = ptr
                    ptr = lidx + 1
                    continue
                ptr += 1
            return left == 0
        
        ans = 0
        while lp < rp:
            mid = (lp+rp+1)//2
            if can(mid):
                lp = mid
            else:
                rp = mid-1
        return lp

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        
        def check(min_force):
            count = 1
            k = position[0]
            for n in position:
                if n-k >= min_force:
                    count += 1
                    k = n
            print(min_force, count)
            if count >= m:
                return True
            return False
        
        
        i, j = 1, position[-1]-position[0]
        while i <= j:
            mid = (i+j)//2
            c1 = check(mid)
            c2 = check(mid+1)
            if c1 and not c2:
                return mid
            if not c1:
                j = mid-1
            else:
                i = mid+1

class Solution:
    def search(s,e,m,l):
        mid=(s+e)//2
        if s>e:
            return e
        return Solution.search(mid+1,e,m,l) if Solution.ispossible(mid,m,l) else Solution.search(s,mid-1,m,l)
    
    def ispossible(n, m, l):
        count=1
        p=l[0]
        for i in range(1,len(l)):
            if l[i]-p >= n:
                count+=1
                p=l[i]
            if count>=m:
                return True
        return False
        
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        return Solution.search(1,position[-1]-position[0], m, position)


class Solution:
    
    def check(self,position,mid,m):
        prev=position[0]
        rem=m-1
        
        i=1
        
        while i<len(position) and rem:
            if position[i]-prev<mid:
                i+=1
                
            else:
                rem-=1
                prev=position[i]
                
                
        return rem==0
    
    def maxDistance(self, position: List[int], m: int) -> int:
        l=1
        h=1000000000
        
        position.sort()
        
        while l<h:
            mid=(l+h+1)//2
            
            if self.check(position,mid,m):
                l=mid
                
            else:
                h=mid-1
                
        return l


class Solution:
    def checkDistance(self, position, minDist, m):
        lastBallPos = position[0]
        ballLeft = m - 1
        i = 1
        while i < len(position) and ballLeft != 0:
            if minDist <= position[i] - lastBallPos:
                lastBallPos = position[i]
                ballLeft -= 1
            i += 1
        return ballLeft == 0
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        print(position)
        high = 1000000000
        low = 1
        ans = 1
        while low < high:
            middle = (high + low + 1) // 2
            if self.checkDistance(position, middle, m):
                low = middle
            else:
                high = middle - 1
            print(high, low)
        return low

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def can_place(force):
            count = 1
            curr = position[0]
            for i in range(1, len(position)):
                if position[i] - curr >= force:
                    count += 1
                    curr = position[i]
            return count
        
        position.sort()
        
        lo, hi = 0, position[-1] - position[0]
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_place(mid) >= m:
                lo = mid
            else:
                hi = mid - 1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left = 1
        right = (position[-1]-position[0]) // (m-1) + 1
        while left<right:
            mid = (left+right)//2
            if self.can(position, mid, m):
                left = mid + 1
            else:
                right = mid
        return left if self.can(position, left, m) else left-1
    
    def can(self, position, mid, m):
        n = len(position)
        pos = [0 for i in range(m)]
        i = 1
        j = 1
        while i < n and j < m:
            if position[i] - position[pos[j-1]] >= mid:
                pos[j] = i
                j += 1
            i += 1
        if j==m:
            return True
        return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
    
    def check(self,position,m,mid):
        
        lastpos=position[0]
        rem=m-1
        
        i=1
        
        while i<len(position) and rem:
            
            if position[i]-lastpos<mid:
                i+=1
                
                
            else:
                rem-=1
                lastpos=position[i]
                
                
        return rem==0
                
    
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        low=1
        high=10**9
        
        while low<high:
            mid=low+(high-low)//2
            
            if self.check(position,m,mid):
                low=mid+1
                
            else:
                high=mid
                
        return low-1
            
        
        


class Solution:
  def maxDistance(self, position: List[int], m: int) -> int:
    # binary search O(NlogQ), n = len(position), q = max(position)
    position.sort()
    def maxBalls(d):
      # O(N), if distance >= d, how many magnetic balls can be placed?
      count, p = 0, -d
      for x in position:
        if x - p >= d:
          count, p = count + 1, x
      return count
    l, r = 0, max(position)
    while l < r:
      d = r - (r - l) // 2
      if maxBalls(d) >= m:
        l = d
      else:
        r = d - 1
    return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        # all_dists = set()
        # for i in range(len(position) - 1):
        #     for j in range(i + 1, len(position)):
        #         all_dists.add(position[j] - position[i])
                
#         all_dists_list = list(all_dists)
#         all_dists_list.sort(reverse=True)

        lo = 1
        hi = position[-1]
        
        while lo < hi:
            dist = (hi + lo) // 2 + 1
         
            if self.maxBalls(position, dist) >= m:
                lo = dist
            else:
                hi = dist - 1
                
            # print(lo, hi)
                
        return lo
                
        
    def maxBalls(self, sorted_position: List[int], distance: int) -> int:
        l_ind = 0
        r_ind = 1
        count = 1
        
        while r_ind < len(sorted_position):
            if sorted_position[r_ind] - sorted_position[l_ind] >= distance:
                count += 1
                l_ind = r_ind
            r_ind += 1
            
        return count

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        # print(position)
        high=int((position[-1]-position[0])/(m-1))
        low=0
        while high-1>low:
            mid=int((high+low)/2)
            # print('high:'+str(high)+'low:'+str(low)+'mid:'+str(mid))
            if self.helper(position,mid,m):
                # print('True')
                low=mid
            else:
                # print('False')
                high=mid-1
        if self.helper(position,high,m):
            return high
        else:
            return low
        
    def helper(self,position,max_d,m):
        count=1
        pre_ind=0
        ind=1
        while ind<len(position):
            if count>=m:
                break
            # print('ind:'+str(ind)+'count:'+str(count))
            if position[ind]-position[pre_ind]<max_d:
                ind+=1
            else:
                pre_ind=ind
                ind+=1
                count+=1
        if count>=m:
            return True
        else:
            return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo, hi = 1, 10**9
        while hi>lo:
            mid = (lo+hi+1)//2
            lapo = position[0]
            co = 1
            for po in position[1:]:
                if po-lapo >= mid:
                    lapo = po
                    co += 1
            if co >= m:
                lo = mid
            else:
                hi = mid-1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        
        def count(d):
            res = 1
            curr = position[0]
            for i in range(1,n):
                if position[i] - curr >= d:
                    res += 1
                    curr = position[i]
            return res
        l = 0
        r = position[-1] - position[0]
        while l < r:
            mid = (l + r + 1) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        arr = sorted(position)
        if m == 2:
            return arr[-1] - arr[0]
        
        def check(n):
            cnt = 2
            pre = arr[0]
            for i in range(1, len(arr) - 1):
                if arr[i] - pre >= n:
                    pre = arr[i]
                    cnt += 1
                    if cnt == m:
                        break
            return cnt == m and arr[-1] - pre >= n
        
        lo, hi = 1, arr[-1] - arr[0]
        while lo <= hi:
            mi = lo + (hi - lo) // 2
            if check(mi):
                lo = mi + 1
            else:
                hi = mi - 1
        return hi

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        def is_good(position, target_distance, m):
            prev = position[0]
            count = 1
            for i in range(1, len(position)):
                pos = position[i]
                if pos - prev >= target_distance:
                    prev = pos
                    count += 1
                    if count == m:
                        return True
            return False
                    
        left = 1
        right = max(position)
        while right > left + 1:
            mid = (left+right)//2
            if is_good(position, mid, m):
                left = mid
            else:
                right = mid
        if is_good(position, right, m):
            return right
        else:
            return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
    
        position.sort()
        
        def count(d):
            curr = position[0]  
            ans = 1
            for i in range(1, len(position)):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:         
            mid = r - (r - l) // 2
            c = count(mid)
            if c >= m:
                l = mid
            else:
                r = mid - 1
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        minp,maxp = min(position),max(position)
        if m == 2:
            return maxp-minp
        
            
        position.sort()
        def valid(i):
  
            count = 1
            ending = position[0]
            for j in range(1,len(position)):
                if position[j] >= ending+i:
                    count += 1
                    ending = position[j]   
           
            return True if count >= m else False
                        

        left,right = 0, maxp-minp+1
        
        while right-left > 1:
            #print(left,right)
            mid = left+(right-left)//2
            if valid(mid):
                left = mid
            else:
                right = mid
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def distributable(n):
            pos = len(position) - 1
            balls = m
            while pos >= 0 and balls:
                balls -= 1
                np = position[pos] - n
                while pos >= 0 and position[pos] > np:
                    pos -= 1
            return not balls       
        position = sorted(position)
        lo, hi = 1, (position[-1] - position[0]) // (m -1) + 1
        ans = lo
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if distributable(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid
        return ans   
        


class Solution:
    def maxDistance(self, pp: List[int], k: int) -> int:
        n=len(pp)
        pp.sort()
        l=1
        r=pp[-1]-pp[0]+1

        def ok(m):
            i=1
            pre=pp[0]
            for _ in range(k-1):
                while i<n and pp[i]-pre<m:i+=1
                if n==i:return False
                pre=pp[i]
                i+=1
            return True

        while l+1<r:
            m=(l+r)//2
            if ok(m):l=m
            else:r=m

        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        def foo( d):
            ans = 1; last = position[0]
            for i in range( 1, len( position)):
                if position[i] - last >= d:
                    ans += 1
                    last = position[i]
            return ans
        
        left = 0; right = position[-1] - position[0]

        while left < right:
            mid = right - ( right - left) // 2
            if foo( mid) >= m:
                left = mid
            else:
                right = mid - 1
        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:            
        position.sort()
        n = len(position)
        
        def check(d):
            k, pre = 1, position[0]
            for i in range(1, n):
                if position[i] - pre >= d:
                    k += 1
                    pre = position[i]
            return k >= m

        lo, hi = 0, position[-1] - position[0]
        while lo < hi:
            mid = hi - (hi - lo) // 2
            if check(mid):
                lo = mid
            else:
                hi = mid - 1
            
        return lo



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def can_reach(force):
            last = position[0]
            placed = 1
            
            for i in range(1, len(position)):
                pos = position[i]
                
                if pos - last >= force:
                    last = pos
                    placed += 1
                if placed >= m:
                    break
            
            return placed >= m
        
        l = 1
        r = position[-1] - position[0] + 1
        
        while l < r:
            mid = (l+r)//2
            if not can_reach(mid):
                r = mid
            else:
                l = mid+1
        
        return l-1
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 0, 10**9 + 2
        while l < r:
            
            mid = (l + r) // 2
            prev = position[0]
            cnt = 1
            for p in position:
                if p >= prev + mid:
                    prev = p
                    cnt += 1
            # print(l, r, mid, cnt)
            if cnt < m:
                r = mid
            else:
                l = mid + 1
        return l-1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def c(p,m,d):
            b=m-1
            l=len(p)
            acc=0
            for i in range(1,l):
                acc+=p[i]-p[i-1]
                if acc>=d:
                    acc=0
                    b-=1
                if b==0:
                    return True
            return False
        low=1
        high=1000000000
        mid=0
        position.sort()
        while low<=high:
            mid=(low+high)//2
            if c(position,m,mid):
                low=mid+1
            else:
                high=mid-1
        return high

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        def possible(num):
            Count, pos = 1, 0

            for i in range(1, len(position)):

                if position[i]  - position[pos] >= num:
                    pos = i
                    Count += 1
                if Count==m:
                    return True

            return Count >= m

        def search(left,right):

            if left == right: 
                return left

            mid = (left + right)//2

            if possible(mid) and not possible(mid + 1):
                return mid
            elif possible(mid): 
                
                return search(mid + 1, right)
            return search(left, mid - 1)

        return search(1, position[-1] - position[0])


class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        positions.sort()
        # try to add balls and record the position
        def check(mid):
            p = 0
            count = 0
            for q in range(len(positions)):
                if positions[q] - positions[p] >= mid:
                    p = q
                    count += 1
            return count >= m-1                  
        
        low, high = 0, positions[-1]-positions[0]
        # print(low, high)
        
        res = 0
        
        while low <= high:
            mid = (low + high)//2
            if check(mid):
                low = mid + 1
                res = max(res, mid)
            else:
                high = mid - 1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
#         def feasible(distance):
#             balls, curr = 1, position[0]
#             for i in range(1, len(position)):
#                 if position[i]-curr >= distance:
#                     balls += 1
#                     curr = position[i]
                    
#             return balls >= m
            
        
#         position.sort()
#         left, right = 0, position[-1]-position[0]
#         while left<right:
#             mid = left + (right-left)//2
#             if feasible(mid):
#                 right = mid
#             else:
#                 left = mid+1
#         return left

        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        lo = 1
        hi = 10**18
        position.sort()
        def func(mid):
            cnt = 1
            cur = position[0]
            for i in range(1,len(position)):
                if position[i]>=cur+mid:
                    cur = position[i]
                    cnt+=1
            if cnt>=m:
                return True
            else:
                return False
            
        while lo<hi:
            mid = (lo+hi)//2
            x = func(mid)
            if x==True:
                lo = mid
            else:
                hi = mid
            if hi-lo==1:
                break
        if func(hi)==True:
            return hi
        return lo
            


class Solution:
    
    def maxDistance(self, position: List[int], m: int) -> int:
        def helper(pos, mid, k):
            temp = pos[0]
            done = 1
            for i in range(1, len(pos)):
                if pos[i] - temp >= mid:
                    temp = pos[i]
                    done += 1
                if done == k:
                    return True
            
            return False
        
        position.sort()
        res = -1
        l, r = 0, position[-1]
        
        while l < r:
            mid = l + (r - l) // 2
            if helper(position, mid, m):
                res = max(res, mid)
                l = mid + 1
            else:
                r = mid
        
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position = sorted(position)
        m_vals = []
        distance = position[-1] - position[0]
        def works(min_dist):
            i = 1
            count = 1
            prev = 0
            while count < m and i < n:
                if position[i] - position[prev] >= min_dist:
                    count += 1
                    prev = i
                i += 1
            return count == m
        
        low = 0
        high = 1 << 32
        while high - low > 1:
            mid = (low + high) // 2
            if works(mid):
                low = mid
            else:
                high = mid - 1
        if works(high):
            return high
        return low


class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        positions.sort()
        def valid(mid):
            count = 0
            last = -math.inf
            for pos in positions:
                if pos >= last + mid:
                    count += 1
                    last = pos
            return count >= m
            
        left, right = 0, positions[-1]
        while left <= right:
            mid = (left + right) // 2
            if valid(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right

# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:            
#         position.sort()
        
#         def check(d):
#             k = 1
#             pre = position[0]
#             for i in range(1, len(position)):
#                 if position[i] - pre >= d:
#                     k += 1
#                     pre = position[i]
#             return k >= m

#         lo, hi = 0, position[-1] - position[0]
#         while lo < hi:
#             mid = (lo + hi)//2
#             if check(mid):
#                 lo = mid
#             else:
#                 hi = mid - 1
            
#         return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l


class Solution:
    def isSafe(self,lst,m,key):
        n = len(lst)
        pre = lst[0]
        index = 1
        while(index<n):    
            while(index<n and lst[index]-pre<key):
                index+=1
            

            m-=1
            if(m==0):
                return True
            if(index==n):
                return False
            pre = lst[index]
            
        
        return False
        
        
            
           
    def maxDistance(self, lst: List[int], m: int) -> int:
        lst.sort()
        n    = len(lst)
        low  = 0
        high = lst[-1] - lst[0]
        ans  = 0
        
        while(low<=high):
            mid = (low+high)//2
            if(self.isSafe(lst,m,mid)):
                ans  = mid
                low  = mid + 1
            else:
                high = mid - 1
        
        return ans
            
            
            
            
            
            


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos.sort()
        n = len(pos)
        def check(gap):
            i = 0
            ii = 0
            nn = 1
            while i < n:
                if pos[i] - pos[ii] >= gap:
                    nn += 1
                    ii = i
                i += 1
            return nn < m
        
        l = float('inf')
        for i in range(n-1):
            l = min(l, pos[i+1] - pos[i])
        r = pos[-1] - pos[0] + 1
        
        while l < r:
            mid = (l + r) // 2
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l - 1
#         if check(l):
#             return l
#         else:
#             return l - 1
            


import numpy as np
import itertools as it
class Solution:
# #     def maxDistance(self, position: List[int], m: int) -> int:
#         arr = np.sort(position)
#         md = max(arr)
#         # print(arr)
        
#         combList = list(it.combinations(arr, m))
#         # print(combList)
#         maxmindiff = 0
#         targetList = []
#         for comb in combList:
#             cb = list(it.combinations(comb, 2))
#             minDiff = md
#             for k in range(len(cb)):
#                 curDiff = abs(cb[k][0]-cb[k][1])
#                 if curDiff< minDiff:
#                     minDiff= curDiff
                
#             if minDiff>maxmindiff:
#                 maxmindiff = minDiff
#                 targetList = comb
#         # print(maxmindiff)
#         # print(targetList)
#         return maxmindiff


    def maxDistance(self, position: List[int], m: int) -> int:
        arr = np.sort(position)
        arr = arr -np.min(arr)
        print(arr)
        def isFeasible(mid, arr, m):
            pos = arr[0]
            n = len(arr)
            count = 1
            for i in range(n):
                if arr[i] - pos>=mid:
                    pos = arr[i]
                    count+=1
                if count>=m:
                    return True
            return False
        
        left = arr[0]
        right = arr[-1]
        
        if m ==2:
            return right-left
        res = -1
        count = 0
        while left < right:
            # mid = np.ceil((right+left)/2)
            mid = (right+left)//2
            # mid = right-(right-left)//2
            # print(mid)
            count +=1
            if isFeasible(mid, arr, m):
                res = max(res,mid)
                left = mid +1
                
            else:
                right = mid
        print(count)
        return int(res)

############################3
# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         n = len(position)
#         position.sort()
        
#         def count(d):
#             ans, curr = 1, position[0]
#             for i in range(1, n):
#                 if position[i] - curr >= d:
#                     ans += 1
#                     curr = position[i]
#             return ans
        
#         l, r = 0, position[-1] - position[0]
#         while l < r:
#             mid = r - (r - l) // 2
#             if count(mid) >= m:
#                 l = mid
#             else:
#                 r = mid - 1
#         return l
       
 



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        low, high = 1, 10 ** 9
        answer = 0
        while low <= high:
            mid = (low + high) >> 1
            cnt = 0
            temp = -(10 ** 9)
            for i in position:
                if i - temp >= mid:
                    cnt += 1
                    temp = i
            if cnt >= m:
                answer = max(answer, mid)
                low = mid + 1
            else:
                high = mid - 1
        return answer


class Solution:
    def fun(self, arr, dist):
        pos = arr[0]
        cows = 1
        for i in range(1, len(arr)):
            e = arr[i]
            if e-pos >= dist:
                pos = e
                cows += 1
            if cows == self.m: return True
        return False
    
    def bs(self, arr):
        lef = 0
        rit = arr[-1]
        while lef < rit:
            mid = (lef+rit)//2
            # print('mid, mid+1', mid, mid+1)
            me = self.fun(arr, mid)
            nex = self.fun(arr, mid+1)
            # print('me, nex', me, nex)
            if me and not nex:
                return mid
            elif me and nex:
                lef = mid + 1
            else:
                rit = mid - 1
            # print('lef, rit', lef, rit)
        return lef
        
    def maxDistance(self, position: List[int], m: int) -> int:
        self.m = m
        position.sort()
        return self.bs(position)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def isFeasible(positions, mid, k): 
            taken = 1
            last = positions[0]
            for i in range(1, len(positions)):
                if positions[i] - last >= mid:
                    taken += 1
                    last = positions[i]
            return taken >= k
        
        def largestMinDist(positions, n, k): 
            low = 0
            high = max(positions) - min(positions) + 1
            while high - low > 1:
                mid = (low + high) // 2
                if isFeasible(positions, mid, k):
                    low = mid
                else:
                    high = mid
            return low
        
        n = len(position) 
        
        position = sorted(position)
        
        '''
        if m == len(position):
            ans = max(position) - min(position)
            for i in range(1, n):
                diff = position[i] - position[i - 1]
                if diff < ans:
                    ans = diff
            return ans
        '''
    
        return largestMinDist(position, n, m)

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l=1
        r=position[-1]
        pos=0
        print((l,r))
        def check(mid):
            cow_cnt=1
            last_pos=position[0]
            for i in range(1,len(position)):
                if position[i]-last_pos>=mid:
                    cow_cnt+=1
                    if cow_cnt==m:
                        return True
                    last_pos=position[i]
            return False
            
        while l<=r:
            mid=l+(r-l)//2
            if check(mid):
                pos=mid
                l=mid+1
                # print(mid)
            else:
                r=mid-1
        return pos


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(pos):
            placed = 1
            i = 0
            j = 1
            while j < l:
                if position[j] - position[i] >= pos:
                    placed +=1
                    if placed == m:
                        return True
                    i = j
                    j = i + 1
                else:
                    j +=1
            return (True if placed == True else False)
                
        l = len(position)
        mx = max(position) - min(position)
        position.sort()
        lo = 1
        hi = mx
        ans = -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if check(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid  - 1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        def check(dist):
            balls = m
            prev = None
            res = float('inf')
            for p in position:
                if prev is None or p - prev >= dist:
                    if prev:
                        res = min(res, p - prev)
                    prev = p
                    balls -= 1

            if balls > 0:
                return None
            return res

        lo, hi = 1, (position[-1] - position[0]) // (m - 1)
        res = 0
        # print('lohi', lo, hi)
        while lo <= hi:
            mid = (lo + hi) // 2
            r = check(mid)
            # print('dist', mid, res)
            if r:
                res = r
                lo = mid + 1
            else:
                hi = mid - 1

        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        mn = sys.maxsize
        mx = position[-1] - position[0]
        
        for i in range(1, len(position)):
            mn = min(mn, position[i] - position[i-1])
            
        def isPoss(diff):
            count = 1
            start = 0
            cd = 0
            f = sys.maxsize
            for i in range(1, len(position)):
                if cd + position[i] - position[i-1] < diff:
                    cd += position[i] - position[i-1]
                else:
                    count += 1
                    f = min(f, position[i] - position[start])
                    start = i
                    cd = 0
                    if count == m:
                        break
                    
            if count == m:
                return f
            return -1
        
        ans = -1
        while mn <= mx:
            mid = (mn + mx)//2
            v = isPoss(mid)
            if v != -1:
                ans = v
                mn = mid + 1
            else:
                mx = mid - 1
        return ans
        
            
            
        


import bisect
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        def possible(gap):
            prev = position[0]
            idx = 0
            left = m - 1
            while left > 0:
                idx = bisect.bisect_left(position, prev+gap, idx + 1, n)
                if idx >= n:
                    return False
                else:
                    prev = position[idx]
                    left -= 1
            return True
        
        position.sort()
        min_gap = 1
        max_gap = position[-1] - position[0]
        while min_gap < max_gap:
            cur_gap = (min_gap + max_gap + 1) // 2
            if possible(cur_gap):
                min_gap = cur_gap
            else:
                max_gap = cur_gap - 1
                
        return min_gap
    


class Solution:
    def maxDistance(self, position, m):
        position.sort()
        n = len(position)
        
        def canFit(gap):
            ct = 1
            i = 0
            j = 1
            while j < n:
                while j<n and position[j]-position[i] < gap:
                    j += 1
                # print(i, j, ct)
                if j<n:
                    ct += 1
                    i = j
                    j += 1
                
                if ct == m:
                    return True
            return False
        
        # print(canFit(999999999))
        
        lo = 1
        hi = position[-1] - position[0]
        res = 0
        ct = 0
        while lo<=hi:
            mid = (lo + hi) >> 1
            ct += 1
            if canFit(mid):
                res = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        if len(position) < m: return 0
        
        position.sort()
        
        def can(force):
            cnt = 1
            pos = 0
            for i in range(1, len(position)):
                if position[i] - position[pos] >= force:
                    cnt += 1
                    pos = i
            return cnt >= m
        
        
        low, high = 0, position[-1] - position[0]
        while low < high:
            mid = (low + high + 1) // 2
            if can(mid):
                low = mid
            else:
                high = mid - 1
        return low

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def feasible(dist, m):
            pre_pos = position[0]
            placed = 1
            for i in range(1, len(position)):
                if position[i] - pre_pos >= dist:
                    placed +=1 
                    if placed >= m:
                        return True
                    pre_pos = position[i]
            return False
            
        l = 1
        r = position[-1] - position[0]
        while l <= r:
            mid = l + (r - l) // 2
            if feasible(mid, m):
                l = mid + 1
            else:
                r = mid - 1
        return l-1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for i in range(1, n):
                if position[i] - curr >= d:
                    ans += 1
                    curr = position[i]
            return ans
        
        l, r = 0, position[-1] - position[0]
        while l < r:
            mid = r - (r - l) // 2
            if count(mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l
        


def possible(min_diff,arr,m):
    start = 0
    total = 1
    end = 1
    while end < len(arr):
        if arr[end]-arr[start] >= min_diff:
            total += 1
            start = end
        
        end += 1
    
    if total >= m:
        return True
    
    return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        ans = -1
        low = 1
        high = 10**9
        while low <= high:
            mid = (low+high)//2
            if possible(mid,position,m):
                low = mid+1
                ans = mid
            else:
                high = mid-1
            
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position = sorted(position)
        i,j = 1,1000000001
        ans = 0 
        while i<=j :
            prevCow = position[0] 
            mid = (i+j)//2 
            currCows = 1 
            for k in range(1,len(position)) : 
                if position[k] - prevCow >= mid : 
                    currCows += 1 
                    prevCow = position[k]
            if currCows < m :
                j = mid - 1
            else :
                i = mid + 1 
                ans = mid 
        return ans 

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def valid(interval,m):
            last=-interval
            for p in position:
                if p-last>=interval:
                    m-=1
                    last=p
            return True if m<=0 else False
        #binary search interval: return the maxiumal interval
        lo,hi=1,max(position)//(m-1) # the interval cannot be than the ideal condition
        while lo<=hi:
            mid=lo+(hi-lo)//2
            if valid(mid,m):# the correct value can be bigger
                lo=mid+1#[min,lo-1] is valid all the time
            else:
                hi=mid-1#[hi+1,max] is not valid all the time
        # lo=hi+1; [min,lo-1] is valid, [lo,max] is not valid
        return hi
        
        
                    


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        
        def count(d):
            cnt = 1
            cur = position[0]
            for p in position[1:]:
                if p>=cur+d: cur, cnt = p, cnt+1
            return cnt
        
        l, r = 0, position[-1]-position[0]
        while l<r:
            mid = r - (r-l)//2
            # count_mid = count(mid)
            # if count(mid) >= m: return r-l
            if count(mid) < m:
                r = mid-1 
            else:
                l = mid
            # print(mid, count(mid))
        return r
            
        
        
        
                    


class Solution:
    def checkDistance(self, position, minDist, m):
        lastBallPos = position[0]
        ballLeft = m - 1
        i = 1
        while i < len(position) and ballLeft != 0:
            if minDist <= position[i] - lastBallPos:
                lastBallPos = position[i]
                ballLeft -= 1
            i += 1
        return ballLeft == 0
    
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        high = position[-1]
        low = 1
        while low < high:
            middle = (high + low + 1) // 2
            if self.checkDistance(position, middle, m):
                low = middle
            else:
                high = middle - 1
        return low

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def isFeasible(mid, arr, n, k): 
            pos = arr[0] 
            elements = 1
  
            for i in range(1, n): 
                if arr[i] - pos >= mid: 
                    pos = arr[i] 
                    elements += 1
  
                    if elements == k: 
                        return True
            return False
        
        position = sorted(position)
        if m == 2:
            return position[-1] - position[0]    
        dist = []
        for i in range(len(position) -1):
            dist.append(position[i+1] - position[i])
        if m == len(position):
            return min(dist)
        
        left = 0
        right = position[-1]
        res = 1
        
        while left < right: 
            mid = (left + right) // 2
         
            if isFeasible(mid, position, len(position), m): 
                res = max(res, mid) 
                left = mid + 1
            else: 
                right = mid 
  
        return res 
        
            
            
            
        


class Solution:
    import bisect
    def maxDistance(self, position: List[int], m: int) -> int:
        l, r = 1, max(position)-min(position)
        if m == 2: return r
        position = sorted(position)
       

        def fea(D):
            #print(\"   \",D)
            s = min(position)
            need = 1
            last = 1
            while(True):
                for i in range(last,len(position)):
                    if position[i]>=s+D:
                        need += 1
                        s = position[i]
                        last = i
                        break
                if last == len(position)-1 or position[-1]<s+D:
                    break
            #print(\" \",need)
            return need
        
        print((fea(2)))
        while(l<r):
            mid = l+(r-l)//2
            if fea(mid)<m:
                r = mid
            else:
                l = mid+1
            
        return l-1
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        # distances = [i for i in range(10**9)]
        # distances.sort()
        
        
        hi = 10**9-1
        li = 0
        while li <= hi:
            # print(\"li \",li,\"hi \",hi)
            if li == hi:
                return li
            mid = (hi+li)//2
            if hi == li+1:
                mid += 1
                
            d = mid
            i = 0
            j = 0
            count = 1
            flag = True

            while count < m:
                while position[j]<position[i] + d:
                    j += 1
                    if j == n and count < m:
                        flag = False
                        break
                if j == n and count <m:
                    flag = False
                    break
                i = j
                count += 1
                
            if hi == li+1:
                if flag:    
                    return hi
                else:
                    return li
            
    
            if flag:
                li = mid
            else:
                hi = mid-1
            
            
                    
    


class Solution:
    def maxDistance(self, arr: List[int], m: int) -> int:
        
        
        arr = sorted(arr)
        low, high = 1, arr[-1]-arr[0]+1
        
        def isValid(k, balls):
            balls-=1
            prev = arr[0]
            res = float('inf')
            for i in range(1,len(arr)):
                if arr[i]-prev >= k:
                    res = min(res, arr[i]-prev)
                    balls-=1
                    prev = arr[i]
                
                if balls == 0: break
                    
            return res if balls == 0 else -1
        
        ans = 0
        
        while low < high:
            mid = low + (high-low)//2
            tmp = isValid(mid, m)
            
            if tmp != -1:
                ans = tmp
                low = mid+1
            else:
                high = mid
        
        return ans
            
            
            
            
            


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        pos = sorted(pos)
        
        def test(gap, pos = pos, m = m):
            cur = pos[0]
            i = 1
            m -= 1
            while i < len(pos):
                if pos[i] - cur >= gap:
                    cur = pos[i]
                    m -= 1
                    if m == 0: return True
                i += 1
            return False
        
        lower, upper = 1, pos[-1]-pos[0]
        if test(upper): return upper
        while True:
            gap = (lower + upper) // 2
            if test(gap): lower = gap
            else: upper = gap
            if upper - lower == 1: return lower

class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        if m < 2: return -1
        pos.sort()
        avg = (pos[-1]-pos[0]+1)//(m-1)+1
        #boolean
        def check(f):
            nonlocal pos, m
            cnt = 0
            pidx = 0
            for i in range(1, len(pos)):
                if (pos[i]-pos[pidx]+1) >= f:
                    cnt += 1
                    pidx = i
            #print(\"cnt:\", cnt)
            return cnt >= m-1

        l, r = 1, avg
        #print(\"l:\", l, \"r:\", r)
        while l+1<r:
            mid = l+(r-l)//2
            if check(mid):
                l = mid
            else:
                r = mid-1
        #print(\"l:\", l, \"r:\", r)
        if check(r): return r-1
        else: return l-1




class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        lo = 1
        hi = position[-1] - position[0]
        res = 0
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            count = 1
            prev = position[0]
            for i in range(1, n):
                if position[i] - prev >= mid:
                    count += 1
                    prev = position[i]
                    
            if count >= m:
                res = max(res, mid)
                lo = mid + 1
            else:
                hi = mid - 1
        return res


class Solution:
    def maxDistance(self, pos: List[int], m: int) -> int:
        
        pos.sort()
        
        low = 0
        
        high = pos[-1] - pos[0]
        
        def chk(d):
            
            nonlocal m
            
            n = len(pos)
            
            c = m            
            p = 0
            
            for i in range(n):
                
                if c == 0:
                    return True
                
                if i == 0:                    
                    c -= 1
                    p = pos[0]                    
                    continue
                    
                if pos[i] - p >= d:
                    c -= 1
                    p = pos[i]
                    
            return c <= 0
        
        
        while low < high:
            
            mid = int( math.ceil( (low + high) / 2 ) )
            
            if chk(mid):
                low = mid
            else:
                high = mid - 1
                
        return low
        
        
                    
            
                    
                    
                
                    
        
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        start = 0
        position.sort()
        end = position[-1]
        def good(x):
            s = -1e100
            count = 0
            for p in position:
                if p - s >= x:
                    count += 1
                    s = p
            return count >= m
        while start < end:
            mid = (start + end) // 2
            if good(mid + 1):
                start = mid + 1
            else:
                end = mid
        return start

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def count(dist):
            prev, balls = -1e9, 0
            for p in position:
                if p - prev >= dist:
                    balls += 1
                    if balls == m:
                        break
                    prev = p
            return balls
        
        position.sort()
        l, r = 1, position[-1]
        res = 0
        while l < r:
            mid = (l + r) // 2
            balls = count(mid)
            if balls == m:
                res = mid
                l = mid + 1
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2:
            return position[-1] - position[0]

        else:
            maxd = position[-1] // (m-1)


        start = 1
        end = maxd

        while start < end:
            middle = (start+end) // 2
            result = self.is_satisfy(position, middle, m)
            if result:
                if start == middle:
                    result2= self.is_satisfy(position, middle+1, m)
                    if result2:
                        return middle + 1
                    else:
                        return middle
                start = middle
            else:
                end = middle - 1

        return start

    def is_satisfy(self, position, maxd, m):
        pre_postion = position[0]
        index = 1
        left_count = m-1

        pcount = len(position)

        while index < pcount:
            if position[index] - pre_postion < maxd:
                index += 1
                continue

            left_count -= 1
            if left_count == 0:
                return True

            pre_postion = position[index]
            index+=1

        return False



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l,r = 1, position[-1]
        while l < r:
            mid = ( r + l +1  ) //2 
            cnter = 0
            lst = - (2*mid)
            for i in position:
                if i - lst >=  mid:
                    cnter += 1
                    lst = i 
            if cnter >= m:
                l = mid
            else:
                r = mid -1
        return l


class Solution:
    # [22,57,74,79]
    def possibleForce (self,force, position):
        count = 0
        lastBall = 0
        for i in range (0,len(position)):
            if (i == 0 or (position[i]- position[lastBall]) >= force):
                count +=1
                lastBall =i
        return  count 
                
            
            
    def maxDistance(self, position: List[int], m: int) -> int:   
        position.sort()
        #print(position)
        maxReally = (position[-1] -position[0] )/ (m-1)
        #print (maxReally)
        maxForce = maxReally
        minForce = 1
        result = -1
        
        while (minForce <= maxForce and minForce >0 and maxForce <= maxReally):
            middleForce = minForce + (maxForce - minForce) // 2
            print((minForce, maxForce, middleForce))
            count =  self.possibleForce(middleForce, position)
            print (count)
            if count >= m:
                # go right
                minForce = middleForce + 1
                result = middleForce
            else:
                # go left
                maxForce = middleForce - 1

        return int(result )
                
                    
                
            
        
        
   
    
    #x o o x o o x - o x
            
             
             


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        result = 0

        # can we place m balls each separated by x distance?
        def check(x) -> bool:
            nonlocal position, m

            last = position[0]
            placed = 1
            for pos in position:
                if pos - last >= x:
                    placed += 1
                    if placed >= m:
                        return True
                    last = pos

            return False



        first = 0
        last = int(ceil((position[-1] - position[0])/(m-1)))
        while first < last:

            mid = (first + last + 1)//2

            if check(mid):
                result = mid
                first = mid
            else:
                last = mid - 1

        return first

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left = 1
        right = position[-1] - position[0]
        
        def countBalls(dist):
            curr, balls = position[0], 1;
            for i in position:
                if (i-curr >= dist):
                    balls += 1
                    curr = i
            return balls
        
        while (left <= right):
            mid = (left + right) // 2
            if (countBalls(mid) >= m):
                left = mid + 1
            else:    
                right = mid - 1
        
        return right
            
            
                
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l = 0
        r = 1 + position[-1] - position[0]
        while l + 1 < r:
            med = (l + r) // 2
            cnt = 0
            pre = position[0] - 2*med
            for x in position:
                if x - pre >= med:
                    pre = x
                    cnt += 1
            if cnt >= m: l = med
            else: r = med
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        positions = sorted(position)
        l, r = 1, positions[len(position) - 1] - positions[0]
        while l < r:
            mid = math.ceil((l + r) / 2)
            if self.balls(positions, mid) >= m:
                l = mid
            else:
                r = mid - 1
        return l

    def balls(self, positions, d):
        curr, ans = -10 ** 10, 0
        for position in positions:
            if position - curr >= d:
                curr = position
                ans += 1
        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m==2:
            return position[-1]-position[0]
        else:
            l=1;r=position[-1]
            while l<r:
                mid=(l+r)//2
                prev,balls=-1000000000,0
                for p in position:
                    if p-prev>=mid:
                        balls+=1
                        if balls==m: break
                        prev=p
                if balls==m:
                    ans=mid
                    l=mid+1
                else: r=mid

        return ans

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def count(dist):
            prev, balls = position[0], 1
            for p in position[1:]:
                if p - prev >= dist:
                    balls += 1
                    if balls == m:
                        break
                    prev = p
            return balls
        
        l, r = 1, position[-1]
        res = 0
        while l < r:
            mid = (l + r) // 2
            balls = count(mid)
            if balls == m:
                res = mid
                l = mid + 1
            else:
                r = mid
        return res

from bisect import bisect_left
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        # log(D) * log(N) * M
        n = len(position)
        position.sort()
        left, right = 1, (position[-1]-position[0])//(m-1)
        ans = 1
        while left <= right:
            mid = (left+right)//2
            #print(left, right, mid)
            head = 0
            remains = m-1
            while remains > 0:
                target = position[head] + mid
                if target > position[-1]:
                    break
                head = bisect_left(position, target, head)
                remains -= 1
                
            if remains == 0:
                #ans = mid
                left = mid+1
            else:
                right = mid-1
                
        return right

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        
        def count(d):
            ans, curr = 1, position[0]
            for x in position[1:]:
                if x - curr >= d:
                    ans, curr = ans+1, x
            return ans
        
        l, r = 1, position[-1] - position[0] + 1
        while l < r:
            p = l + (r - l) // 2
            if count(p) >= m: l = p+1
            else: r = p
        return l-1

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2:
            return position[-1] - position[0]
        
        def count(dist):
            prev, balls = position[0], 1
            for p in position[1:]:
                if p - prev >= dist:
                    balls += 1
                    if balls == m:
                        break
                    prev = p
            return balls
        
        l, r = 1, position[-1]
        res = 0
        while l < r:
            mid = (l + r) // 2
            balls = count(mid)
            if balls == m:
                res = mid
                l = mid + 1
            else:
                r = mid
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
#         def pd(i, m):
#             if m == 1:
#                 return float(\"inf\")
            
#             if memo[i][m]:
#                 return memo[i][m]
            
#             res = 0
            
#             for j in range(i+1, len(position)):
#                 res = max(res, min(position[j] - position[i], pd(j, m-1)))
                
#             memo[i][m] = res
            
#             return res
        
#         position = sorted(position)
        
#         memo = [(1 + m) * [0] for _ in range(1 + len(position))]
        
#         res = pd(0, m)
    
        position = sorted(position)
        
        if m == 2:
            return position[-1] - position[0]
        
        def solve(threshold, m):
            last_ball_pos = position[0]
            tot = 1
            
            for pos in position:
                if pos - last_ball_pos >= threshold:
                    tot += 1
                    last_ball_pos = pos
                
            return tot >= m
        
        start = 0
        end = position[-1] - position[0]
        
        res = 0
        
        while start <= end:
            middle = start + (end - start) // 2
                
            if solve(middle, m):
                start = middle + 1
                res = max(res, middle)
                
            else:
                end = middle - 1
    
        return res

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        
        position.sort()
        maxForce = (position[-1] - position[0]) // (m - 1)
        minForce = 1        
        
        while maxForce > minForce:
            maxMinForce = (maxForce + minForce + 1) // 2
            #print(minForce, maxForce, maxMinForce)
            if self.canPut(position, m, maxMinForce):
                minForce = maxMinForce
            else:
                maxForce = maxMinForce - 1
        
        return minForce
    
    def canPut(self, position: List[int], m: int, force: int) -> bool:
        putCnt = 0
        prePos = -1
        for pos in position:
            if prePos == -1 or pos - prePos >= force:
                putCnt += 1
                prePos = pos
                if putCnt == m:
                    return True
        
        return False

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)
        max_possible = (position[-1] - position[0]) // (m - 1)
        right = max_possible
        left = 0
        mid = max_possible // 2
        while left <= right:
            if self.check(position, m, mid):
                left = mid + 1
                mid = (left + right) // 2
            else:
                right = mid - 1
                mid = (left + right) // 2
        
        return mid
        
    
    def check(self, position, m, force):
        p = 1
        m -= 1
        prev_pos = position[0]
        while p < len(position):
            if position[p] - prev_pos >= force:
                m -= 1
                prev_pos = position[p]
            if not m:
                return True
            p += 1
        return False



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left = 1
        right = position[-1] - position[0]
        
        def countBalls(dist):
            curr, balls = position[0], 1;
            for i in position:
                if (i-curr >= dist):
                    balls += 1
                    curr = i
            return balls
        
        while (left <= right):
            mid = (left + right) // 2
            
            if (countBalls(mid) >= m):
                left = mid + 1
            else:    
                right = mid - 1
        
        return right
            
            
                
        


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[-1] - position[0]
        
        def isValid(val):
            ball = 1
            previous = position[0]
            for p in position:
                if p - previous < val:
                    continue
                ball += 1
                previous = p
            return ball >= m
        
        while l < r:
            mid = l + (r - l + 1) // 2
            if isValid(mid):
                l = mid
            else:
                r = mid - 1
        return r

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2: return position[-1] - position[0]
        l, r = 1, position[-1]
        ans = 0
        while l < r:
            mid = (l + r) // 2
            prev, balls = -1000000000, 0
            for p in position:
                if p - prev >= mid:
                    balls += 1
                    if balls == m: break
                    prev = p
            if balls == m:
                ans = mid
                l = mid + 1
            else:
                r = mid
        return ans
        
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        if m == 2: return position[-1] - position[0]
        l, r = 1, position[-1]
        ans = 0
        while l < r:
            mid = (l + r) // 2
            prev, balls = -1000000000, 0
            for p in position:
                if p - prev >= mid:
                    balls += 1
                    if balls == m: break
                    prev = p
            if balls == m:
                ans = mid
                l = mid + 1
            else:
                r = mid
        return ans
        


class Solution:
    def maxDistance(self, a: List[int], m: int) -> int:        
        def check(d):
            x, k = 0, m            
            for i in range(len(a)):
                if a[i] >= x: 
                    x, k = a[i] + d, k - 1
                    if k == 0: break                             
            return k == 0            
        a.sort()                
        l, r = 1, (max(a) - min(a)) // (m-1)                        
        while l + 1 < r:
            d = (l + r) // 2            
            if check(d): l = d
            else: r = d - 1                            
        return r if check(r) else l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        res = 0
        l, r = 1, (position[-1] - position[0]) // (m - 1) + 1
        
        while l < r:
            mid = (l + r) // 2
            prev = position[0]
            ball = 1
            for i in position[1:]:
                if i - prev >= mid:
                    ball += 1
                    if ball == m:
                        break
                    prev = i
                    
            if ball == m:
                l = mid + 1
                res = mid
            else:
                r = mid
        return res
        
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def ball_count(distance):
            prev,cnt=position[0],1
            for pos in position[1:]:
                if pos-prev>=distance:
                    cnt+=1
                    prev=pos
            return cnt
                
            
            
            
            
        position.sort()
        n=len(position)
        l,r=0,position[-1]-position[0]
        while l<r:
            mid=r-(r-l)//2
            if ball_count(mid)>=m:
                l=mid
            else:
                r=mid-1
        return l
        


import bisect
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        position_set = set(position)
        position.sort()
        max_force = (position[-1] - position[0])//(m-1)
        min_force = 1
        last_idx = len(position)-1
        
        
        while min_force != max_force:
            mid_force = (min_force + max_force + 1) // 2
            first_ball = next_ball = position[0]
            next_idx = 1
            
            for _ in range(m-2):
                next_ball = first_ball+mid_force
                
                if next_ball not in position_set:
                    
                    # search the next larger
                    next_idx = bisect.bisect_left(position, next_ball, next_idx, last_idx)
                    next_ball = position[next_idx]
                    if next_idx == last_idx:
                        break

                next_idx += 1
                first_ball = next_ball
            else:
                if position[-1] - next_ball >= mid_force:
                    min_force = mid_force
                else:
                    max_force = mid_force-1
                continue
            max_force = mid_force-1
        
        return min_force
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def check(dist, m):
            last = position[0]
            for i in range(1, len(position)):
                if(position[i]-last >= dist):
                    m-=1
                    last=position[i]
            return(m<=1)
        l=0; r=position[-1]-position[0]
        while(l<r):
            mid=l+((r-l+1)>>1)
            if(check(mid, m)):
                l=mid
            else:
                r=mid-1
        return(l)

class Solution:
    def maxDistance(self, positions: List[int], m: int) -> int:
        positions.sort()

        def check(value) -> bool:
            last = positions[0]
            count = 1

            for pos in positions:
                if pos-last > value:
                    count += 1
                    last = pos
                    if count >= m:
                        return False

            return True

        left, right = 1, max(positions)
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        #求两球之间的最小最大值
        position.sort()
        l,r=0,position[-1]-position[0]  #两球之间的距离
        while l<r:
            mid=(l+r+1)//2
            count=1
            last=position[0]
            for a in position[1:]:
                if a-last>=mid:
                    count+=1
                    last=a
            if count<m:
                r=mid-1
            else:
                l=mid
        return l

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        
        def canPut(distance: int)->bool:
            count = 1
            curr = position[0]
            for pos in position[1:]:
                if pos >= curr+distance:
                    count += 1
                    curr = pos
                    if count >= m:
                        return True
            return False
        
        position.sort()
        lo, hi = 1, position[-1]-position[0]
        max_distance = lo
        
        while lo <= hi:
            mi = (lo+hi)//2
            if canPut(mi):
                lo = mi+1
                max_distance = max(max_distance, mi)
            else:
                hi = mi-1
            #print(lo, hi)
        
        return max_distance
            


class Solution:
    def maxDistance(self, a: List[int], m: int) -> int:        
        def check(d):
            x, k = 0, m            
            for i in range(len(a)):
                if a[i] >= x: 
                    x, k = a[i] + d, k - 1
                    if k == 0: break                             
            return k == 0            
        a.sort()                
        l, r = 1, (max(a) - min(a)) // (m-1)                        
        while l + 1 < r:
            d = (l + r) // 2            
            if check(d): l = d
            else: r = d - 1                            
        return r if check(r) else l


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def working(mid: int):
            prev_stall = 0
            stall = 1
            # print(position)
            for i in range(1, m):
                while (position[stall] - position[prev_stall]) < mid:
                    stall+=1
                    if stall == len(position):
                        return False
                prev_stall = stall
            
            return True
        
        L = max(position)
        
        low = 1
        high = int(L/(m-1))
        largest = 0
        position = sorted(position)
        
        while low <= high:
            mid = int((low+high)/2)
            
            if working(mid):
                if mid < int(L/(m-1)):
                    low = mid + 1
                else:
                    largest = max(largest, mid)
                    break
                largest = max(largest, mid)
            elif mid > 0:
                high = mid - 1
        
        return largest
                


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)
        left,right = 0,position[-1]-position[0] // (m-1) # search space is sorted
        def count_balls(force):
            balls,prev = 1,position[0]
            for cur in position[1:]:
                if cur-prev >= force:
                    balls += 1
                    prev = cur
            return balls
        while left < right:
            # mid = left + (right-left)//2
            mid = right - (right-left) // 2
            # mid = (left+right+1)//2
            if count_balls(mid) >= m:
                left = mid
            else:
                right = mid - 1
        return left

            
            
            
            


class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        left = 1
        right = max(position)
        position.sort()
        
        while left < right:
            mid = left + (right - left)//2
            legal = self.evaluate(position, m, mid)
            if legal:
                right = mid 
            else:
                left = mid + 1
        
        return left - 1
            
            
    def evaluate(self, position, m, force):
        balls_placed = 0 
        prev_val = None
        for val in position:
            if not prev_val:
                prev_val = val
                balls_placed += 1
            else:
                if val - prev_val >= force:
                    balls_placed += 1
                    prev_val = val
        if balls_placed > m-1:
            return False
        return True

import math
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        diff = []
        for i in range(n-1):
            diff.append(position[i+1]-position[i])
        
        def check(force,diff,num):
            i = 0
            j = 0
            curr = 0
            while i < len(diff):
                curr += diff[i]
                if curr >= force:
                    j += 1
                    curr = 0
                i += 1
            return j >= num
        
        if m == 2:
            return position[n-1]-position[0]
        
        start = 1
        end = math.ceil((position[n-1]-position[0])/(m-1))
        mid = (start+end)//2
        ansList = []
        while start < end:
            if check(mid,diff,m-1):
                start = mid+1
                ansList.append(mid)
            else:
                end = mid-1
            mid = (start+end)//2
        if check(mid,diff,m-1):
            ansList.append(mid)
        return max(ansList)
                



class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l, r = 1, position[len(position) - 1] - position[0]
        def is_doable(gap):
            count, pre  = 0, position[0] - 2 * gap, 
            for element in position:
                if element - pre >= gap:
                    pre = element
                    count += 1
                    if count == m:
                        return True
            return False
            
        while True:
            mid = (l + r) // 2
            if is_doable(mid):
                if mid == position[len(position) - 1] - position[0]:
                    return mid
                elif is_doable(mid + 1):
                    l = mid + 1
                else:
                    return mid
            else:
                r = mid - 1
            


class Solution:
    def maxDistance(self, position: List[int], k: int) -> int:
        position.sort()
        def check(m):
            prev = -1e20
            c = 0
            for i in position:
                if i - prev >= m:
                    prev = i
                    c+=1
            return c>=k
        l = 0
        r = max(position)
        while l < r:
            m = (l+r+1)//2
            if check(m):
                l = m
            else:
                r = m-1
        return l