from sortedcontainers import SortedList
class MaxMap:
    m = defaultdict(set)
    h = []
    
    def add(self,k,v):
        h,m = self.h,self.m
        m[k].add(v)
        heappush(h,(-v,k))

    def delete(self,k):
        h,m = self.h,self.m
        if k in m:
            m.pop(k)

    def get(self):
        h,m = self.h,self.m
        while h:
            v,k = h[0]
            if k not in m or -v not in m[k]:
                heappop(h)
                continue
            return -v,k
        return None,None
    

class ExamRoom:
    def __init__(self, n: int):
        self.A = SortedList()
        self.M = MaxMap()
        self.A.add(-1)
        self.A.add(n)
        self.M.add((-1,n),n)
        self.n = n

    def seat(self) -> int:
        maxv,pair = self.M.get()
        left,right = pair
        self.M.delete((left,right))
        if left == -1:
            self.add(left+1,right)
            self.A.add(0)
            return 0
        elif right == self.n:
            self.add(left,right - 1)
            self.A.add(self.n - 1)
            return self.n - 1
        else:
            mid = left + right >> 1
            
            if mid > left + 1:
                self.add(left,mid)
            if mid < right - 1:
                self.add(mid,right)
            self.A.add(mid)
            return mid
        
    def leave(self, p: int) -> None:
        index = self.A.bisect_left(p)
        left,mid,right = self.A[index-1],self.A[index],self.A[index+1]
        self.M.delete((left,mid))
        self.M.delete((mid,right))
        self.add(left,right)
        if p in self.A:
            self.A.remove(p)
    
    def add(self,left,right):
        size = max(0,right - left - 2) if left == -1 or right == self.n else right - left - 2 >> 1
        self.M.add((left,right),size)

# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)