855

struct interval{
    static int N;
    int l, r;
    interval(int l, int r) : l(l), r(r) {}
    int getDist()const{
        if(l == 0) return r;
        if(r == N - 1) return N - 1 - l;
        if(r < l) return -1;
        else return (r - l) / 2;
    }
    int getPos()const{
        if(l == 0) return 0;
        if(r == N - 1) return N - 1;
        else return l + (r - l) / 2;
    }
    bool operator <(const interval& a)const{
        int d1 = getDist(), d2 = a.getDist();
        if(d1 != d2) return d1 > d2;
        return l < a.l;
    }
};

int interval::N = 0;
class ExamRoom {
public:
    set<interval> intervals;
    map<int, int> l2r, r2l;

    ExamRoom(int N){
        interval::N = N;
        intervals.insert(interval(0, N - 1));
        l2r[0] = N - 1;
        r2l[N - 1] = 0;
    }

    int seat(){
        interval cur = *(intervals.begin());
        intervals.erase(intervals.begin());

        int pos = cur.getPos();
        intervals.insert(interval(cur.l, pos - 1));
        intervals.insert(interval(pos + 1, cur.r));
        l2r[cur.l] = pos - 1; r2l[pos - 1] = cur.l;
        l2r[pos + 1] = cur.r; r2l[cur.r] = pos + 1;
        return pos;
    }

    void leave(int p){
        int l = r2l[p - 1], r = l2r[p + 1];
        intervals.erase(interval(l, p - 1));
        intervals.erase(interval(p + 1, r));
        intervals.insert(interval(l, r));
        l2r[l] = r; r2l[r] = l;
        r2l.erase(p - 1); l2r.erase(p + 1);
    }
};
/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom* obj = new ExamRoom(n);
 * int param_1 = obj->seat();
 * obj->leave(p);
 */