class Solution {
    public int maxDistToClosest(int[] seats) {
        int i = 0, n = seats.length, j = n - 1;
        while (seats[i] == 0) i++;
        int res = i;
        while (seats[j] == 0) j--;
        res = Math.max(res, n - j - 1);
        for (int k = i + 1; k <= j; k++) {
            if (seats[k] == 1) {
                res = Math.max(res, (k - i) / 2);
                i = k;
            }
        }
        return res;
    }
}

class ExamRoom {
    int n;
    TreeSet<Integer> s = new TreeSet(); // 入座的座位号
    // 获取最大区间，优先左侧
    PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b) -> {
            int x = (a[1] - a[0]) / 2, y = (b[1] - b[0]) / 2;
            return x == y ? a[0] - b[0] : y - x;
            //return x < y || (x == y && a[0] > b[0]) ? 1 : -1;
        });

    public ExamRoom(int n) {
        this.n = n;
    }

    public int seat() {
        if (s.isEmpty()) {
            s.add(0);
            return 0;
        }
        // 延迟删除无效区间
        while (!q.isEmpty() && (!s.contains(q.peek()[0]) || !s.contains(q.peek()[1]) || s.higher(q.peek()[0]) != q.peek()[1])) {
            q.poll();
        }
        int p = 0, left = s.first(), right = n - 1 - s.last();
        if(!q.isEmpty()){
            int[] t = q.peek();
            // 向上取整
            int d = (t[1] - t[0]) / 2;
            if(d > left && d >= right){
                p = t[0] + d;
                q.offer(new int[]{t[0], p});
                q.offer(new int[]{p, t[1]});
                s.add(p);
                return p;
            }            
        }        
        if (right > left) { // 最右的位置更优
            p = n - 1;
            q.offer(new int[]{s.last(), p});
        } else {
            q.offer(new int[]{0, s.first()});
        }
        s.add(p);
        return p;
    }

    public void leave(int p) {
        // 不是两端填加区间
        if (p != s.first() && p != s.last()) {
            q.offer(new int[]{s.lower(p), s.higher(p)});
        }
        s.remove(p);
    }
}