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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

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):
			if k > n - i:
				return 0
			if k == 1:
				return position[n - 1] - position[i0]
			if k == 0:
				return 1e+20
			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

		@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

		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:
		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:
		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
		r = position[-1] - position[0]
		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, 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:

		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)
		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


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)
		l = 1
		r = max_possible_answer + 1
		while l < r:
			mid = math.ceil((r + l) / 2)
			if self.is_possible(position, m, mid):
				l = mid
			else:
				r = mid - 1
		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 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
			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:

		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:
				left = mid + 1
			elif num_balls == m:
				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 - prev >= mid:
				m += 1
				prev = i
		return m


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:
		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()

		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


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:
		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:

		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:
		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:
		position.sort()

		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
		(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 isfail(mid):
			ans = 1
			curr = 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 - left) // 2
			if isfail(mid):
				right = mid
			else:
				left = mid + 1
		return left - 1


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]
				elif 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:
		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:
		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)
		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
			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:
		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
			if condition(mid):
				left = mid + 1
			else:
				right = mid
		if condition(left):
			return left
		else:
			return left - 1
		return left


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:
		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:

		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:
		position.sort()
		lo = 1
		hi = position[-1] - position[0]
		while lo < hi:
			mid = (lo + hi + 1) // 2
			if self.check(position, mid, m):
				lo = mid
			else:
				hi = mid - 1
		return hi

	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, 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:

		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 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:
					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


class Solution:

	def maxDistance(self, position: List[int], m: int) -> int:
		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
		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
		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


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, 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:
		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:
		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))

		def helper(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
		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)
		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()
		result = 0

		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


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):
				left = mid
				res = max(res, mid)
			else:
				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()
		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
			if checkPossible(mid):
				ans = mid
				l = mid + 1
			else:
				r = mid
		return ans


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:
		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
			if isOK(mid):
				left = mid
			else:
				right = mid - 1
		return right


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()
		(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, 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


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, 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:

		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, 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()
		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:
						return True
					pre_dis = 0
				else:
					pre_dis += distance[i]
			return False
		while left < right:
			mid = (left + right + 1) // 2
			if check(mid, m) == True:
				left = mid
			else:
				right = mid - 1
		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:
					last = position[i]
					count += 1
			return count >= m
		while left < right:
			mid = (right - left + 1) // 2 + left
			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)

		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)
		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]
			if placed >= m:
				answer = mid
				l = mid + 1
			else:
				r = mid - 1
		return answer


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 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):
				left = mid + 1
			else:
				right = mid
		return res


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:
			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:
		position.sort()
		lo = 1
		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, 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
		(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])

		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 = right - (right - left) // 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
			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:
		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
		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: List[int], m: int) -> int:
		position.sort()
		n = len(position)

		def distance(d):
			p = 0
			c = 1
			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
			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: 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 = 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()
		(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):
			balls_to_place = m - 1
			last_ball_pos = 0
			for ind in range(last_ball_pos, len(position)):
				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
		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 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()
		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):
				if position[i] - last >= guess:
					placed += 1
					last = position[i]
				if placed == m:
					return True
				i += 1
			return placed >= m
		position.sort()
		l = 0
		r = position[-1] - position[0]
		while l < r:
			mid = (l + r + 1) // 2
			if guess(position, m, mid):
				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:
		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):
		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:
		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)
			elif 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 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


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):
		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
			if self.helper(mid, position, m):
				left = mid + 1
			else:
				right = mid
		return left - 1


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:
		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
		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
		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


class Solution:

	def maxDistance(self, arr: List[int], m: int) -> int:
		arr.sort()
		low = 1
		high = arr[-1] - arr[0]

		def place(limit):
			prev = -10000000000.0
			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)
			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:
			mid = l + r >> 1
			if helper(mid) == m:
				res = max(mid, res)
				l = mid + 1
			elif helper(mid) > m:
				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
		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:

		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:
		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
		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()

		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:

	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:
					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
				elif abs(prev - position[i]) < gap:
					continue
				else:
					prev = position[i]
					balls -= 1
			if balls <= 0:
				return True
			return False
		while 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 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:
			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
		return L


class Solution:

	def maxDistance(self, position: List[int], m: int) -> int:
		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]
		(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):
		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()
		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, position: List[int], m: int) -> int:
		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 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(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()

		def check(dist: int) -> bool:
			curr = position[0]
			count = 1
			for i in range(len(position)):
				if abs(position[i] - curr) >= dist:
					curr = position[i]
					count += 1
				if i == len(position) - 1:
					if count >= m:
						return True
					else:
						return False
		lo = 1
		hi = max(position) - min(position)
		while lo < hi:
			mid = lo + (hi - lo + 1) // 2
			if check(mid):
				lo = mid
			else:
				hi = mid - 1
		return lo


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 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
		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()
		(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:

		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
			if Valid(mid):
				l = mid + 1
			else:
				r = mid - 1
		return l - 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):
			balls = [position[0]]
			placed = 1
			i = 1
			while i <= len(position) - 1:
				if position[i] - balls[-1] >= d:
					balls.append(position[i])
					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
			if Solution.isSolution(self, m, position, average):
				minDist = average
			else:
				maxDist = average
		if Solution.isSolution(self, m, position, maxDist):
			return maxDist
		else:
			return minDist


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):
					return 0
				last = j
			return 1
		while l < r:
			mid = (r + l) // 2
			dist = c(mid)
			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, 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:

		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:
		position = sorted(position)
		lo = 1
		hi = position[-1] - position[0]
		while lo < hi:
			mid = (lo + hi + 1) // 2
			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):
			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:
		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
			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
		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 left


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
		return ans


class Solution:

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

		def isValid(f, k):
			pos = position[0]
			count = 1
			for i in range(1, n):
				if position[i] - pos >= f:
					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:

		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]
			elements = 1
			for i in range(1, len(arr)):
				if arr[i] - pos >= mid:
					pos = arr[i]
					elements += 1
					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:

		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:
			next_valid_pos = position[0] + gap
			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
		position.sort()
		max_gap = (position[-1] - position[0]) // (m - 1)
		min_gap = min((position[i] - position[i - 1] for i in range(1, size)))
		if m == 2:
			return max_gap
		(left, right) = (min_gap, max_gap)
		while left <= right:
			gap_trial = left + (right - left) // 2
			if satisfy(gap=gap_trial):
				left = gap_trial + 1
			else:
				right = gap_trial - 1
		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
		while l < r:
			mid = l + (r - l) // 2
			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()
		(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:

		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):
				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:
		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:
						return True
			return False
		position = sorted(position)
		(low, high) = (0, position[-1])
		output = -1
		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:
		position = sorted(position)
		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
			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:
		position.sort()

		def helper(position, x, m):
			prev = position[0]
			m -= 1
			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 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()
		(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
		position.sort()
		(lo, hi) = (0, position[-1] - position[0])
		while lo < hi:
			mid = hi - (hi - lo) // 2
			if validPlacement(mid):
				lo = mid
			else:
				hi = mid - 1
		return lo


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 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 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:
		position.sort()

		def maxBalls(d):
			(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()
		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
		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()
		high = int((position[-1] - position[0]) / (m - 1))
		low = 0
		while high - 1 > low:
			mid = int((high + low) / 2)
			if self.helper(position, mid, m):
				low = mid
			else:
				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
			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:
		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:
		(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:
			mid = left + (right - left) // 2
			if valid(mid):
				left = mid
			else:
				right = mid
		return left


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
			if cnt < m:
				r = mid
			else:
				l = mid + 1
		return l - 1


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()

		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])
		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:
		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 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


import numpy as np
import itertools as it

class Solution:

	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 = (right + left) // 2
			count += 1
			if isFeasible(mid, arr, m):
				res = max(res, mid)
				left = mid + 1
			else:
				right = mid
		print(count)
		return int(res)


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
			me = self.fun(arr, mid)
			nex = self.fun(arr, mid + 1)
			if me and (not nex):
				return mid
			elif me and nex:
				lef = mid + 1
			else:
				rit = mid - 1
		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)
		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
			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
		while lo <= hi:
			mid = (lo + hi) // 2
			r = check(mid)
			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


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
				if j < n:
					ct += 1
					i = j
					j += 1
				if ct == m:
					return True
			return False
		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


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
		(lo, hi) = (1, max(position) // (m - 1))
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if valid(mid, m):
				lo = mid + 1
			else:
				hi = mid - 1
		return hi


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):
			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
			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)
		hi = 10 ** 9 - 1
		li = 0
		while li <= 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

		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
			return cnt >= m - 1
		(l, r) = (1, avg)
		while l + 1 < r:
			mid = l + (r - l) // 2
			if check(mid):
				l = mid
			else:
				r = mid - 1
		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 = -1e+100
			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:
		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:

	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()
		maxReally = (position[-1] - position[0]) / (m - 1)
		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:
				minForce = middleForce + 1
				result = middleForce
			else:
				maxForce = middleForce - 1
		return int(result)


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()

		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:
		n = len(position)
		position.sort()
		(left, right) = (1, (position[-1] - position[0]) // (m - 1))
		ans = 1
		while left <= right:
			mid = (left + right) // 2
			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:
				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:
		n = len(position)
		position.sort()
		maxForce = (position[-1] - position[0]) // (m - 1)
		minForce = 1
		while maxForce > minForce:
			maxMinForce = (maxForce + minForce + 1) // 2
			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:

		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:
					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
		return max_distance


class Solution:

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

		def working(mid: int):
			prev_stall = 0
			stall = 1
			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:
		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
			elif 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 = -1e+20
			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