Assign seats to maximize distance to nearest occupied seat (online, no rearrangement)

Problem: Online seat assignment to maximize distance (no rearrangement) There are n seats in a row labeled 0..n-1. Employees arrive one by one. Each time you must assign an empty seat following the rule: Choose a seat that maximizes the distance to the nearest occupied seat. If multiple seats achieve the same maximum distance, choose the smallest index. Once assigned, seats cannot be rearranged later. Implement: class AssignSeat: def __init__(self, n: int): pass def assign(self) -> int: """Return the seat index assigned this time.""" pass Example seats = AssignSeat(10) seats.assign() -> 0 seats.assign() -> 9 seats.assign() -> 4 (or 5 depending on tie-break; with smallest-index tie-break it is 4) Typical Constraints 1 <= n <= 1e9 (or smaller depending on implementation) Number of assign() calls m: 1 <= m <= min(n, 2e5) Target complexity: O(log m) per assign() Complete the implementation according to the rules above. Example Input n=10 assign x3 Output 0 9 4